Beefy Boxes and Bandwidth Generously Provided by pair Networks
XP is just a number

Re^2: does perl have branch prediction

by david2008 (Scribe)
on Jan 29, 2014 at 06:44 UTC ( #1072442=note: print w/replies, xml ) Need Help??

in reply to Re: does perl have branch prediction
in thread does perl have branch prediction

How can we explain the small time difference between the sorted and unsorted array summing?

Replies are listed 'Best First'.
Re^3: does perl have branch prediction
by BrowserUk (Pope) on Jan 29, 2014 at 07:06 UTC
    How can we explain the small time difference between the sorted and unsorted array summing?

    It is almost certainly down to the cpu instruction cache.

    1. With the sorted array, on average:

      for the first half of the array, the instructions required in the loop will already be in the cache.

      Then there will be a need to load the required instructions into the cache, once, when the break point is reached, and they will remain there for the second half of the array.

    2. With the unsorted array,

      the instruction cache potentially might need to be flushed and repopulated for every other iteration of the loop.

    Please note, that is just my best guess. I can't think of any easy -- or even feasible given what hardware and software I have available to me -- way of attempting to verify my hypothesis.

    With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'
    Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
    "Science is about questioning the status quo. Questioning authority".
    In the absence of evidence, opinion is indistinguishable from prejudice.
Re^3: does perl have branch prediction
by SimonPratt (Friar) on Jan 29, 2014 at 11:12 UTC

    Its all to do with the workflow at a hardware level. I cant remember specifically all of the stages of processing, but suffice it to say that there are multiple stages of processing. When a program comes to a branch (such as an if), it doesnt pause the processing input for however many cycles, just to wait for the result of the if to pop out the end, it instead uses branch prediction to choose a path to go down (really useful if you're running in a loop, not so useful otherwise) and shovels the next instruction into the first stage of processing. When the branch is finally resolved, it determines whether the results from the next instruction are kept or discarded.

    If you look at the if you are doing and the dataset, it becomes obvious that a sorted dataset will optimise the branch prediction ability of the CPU, resulting in a minor performance difference (becoming larger as the dataset grows), however as pointed out, sorting the dataset is a lot more costly than the performance gained. (and this is because you are looking at performing many more cycles of processing to sort each item in the array than you will actually save)

Re^3: does perl have branch prediction
by roboticus (Chancellor) on Jan 29, 2014 at 11:53 UTC


    Various sort algorithms have different performance based on the order of the incoming data, so you don't need branch prediction to explain it.


    When your only tool is a hammer, all problems look like your thumb.

Log In?

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://1072442]
and the universe expands...

How do I use this? | Other CB clients
Other Users?
Others cooling their heels in the Monastery: (6)
As of 2018-06-22 19:37 GMT
Find Nodes?
    Voting Booth?
    Should cpanminus be part of the standard Perl release?

    Results (124 votes). Check out past polls.