3 ms·

I feel like branch prediction is only a small part of the performance boost. If I do the same in python 2500 times for an array of size 40k, I get 0.0018351996

I feel like branch prediction is only a small part of the performance boost. If I do the same in python 2500 times for an array of size 40k, I get 0.00183519964218 vs 0.00163079910278 or ~11% boost. I imagine the 6x factor probably is because the optimizer unfolds the array/loop structure. edit: sorting the array increases the time by about 4x if you include the sort time, so its not worth it

hyperpape 9y ago
You can't use the Python implementation to get insight into what's happening with a C++ implementation, because the overhead of operations in Python may mask a real effect that can be seen in C++.
- autokad 9y ago
  not directly, but information is information. I am also more skeptical that branching alone would result in a 6x increase in run time. We know optimizes unfold loops as well as arrays. it doesnt take a profound leap in logic that the optimizer may have unfolded everything and realized certain code was not going to change the state of the program, thus removed it. Maybe it didnt, but then again maybe it did.
  - hyperpape 9y ago
    > information is information It's information, but not worthwhile information. > It doesnt take a profound leap in logic that the optimizer may have unfolded everything and realized certain code was not going to change the state of the program, thus removed it. Maybe it didnt, but then again maybe it did. Prove it. This article has had a ton of traffic. If you see the thing that everyone missed, a lot of people will be very impressed with you.
  - Ultimatt 9y ago
    Did you try with an actual array or a Python list? https://docs.python.org/3/library/array.html https://docs.python.org/3/library/array.html or numpy you might be able to recover the same effect. Your average line of Python is miles away from low level and simple operations. Pretty much any dynamic language with a large runtime is. Especially when they default to lists not arrays. You should see your result as evidence of that. Not assume this discussion is flawed.
corysama 9y ago
I'm surprised you got such a high (11%) boost. I would not expect branch prediction issues from your code to have much of an effect in Python because the Python interpreter itself naturally introduces 10x as many branches under the hood as the code it interprets.
- winstonewert 9y ago
  guess: the branches in the python VM are more accurately predicted than branch on the data. The data is going to be random and thus unpredictable, but the branches in the VM are probably pretty predictable.
  - dom0 9y ago
    Python if statements will branch on very few processor instructions in the VM; so I don't think branch prediction of the processor is able to predict different Python if's — they're all the same to it. Well, that... and even simple Python VM instructions tend to take dozens of insns to execute.

hyperpape 9y ago

You can't use the Python implementation to get insight into what's happening with a C++ implementation, because the overhead of operations in Python may mask a real effect that can be seen in C++.

autokad 9y ago
not directly, but information is information. I am also more skeptical that branching alone would result in a 6x increase in run time. We know optimizes unfold loops as well as arrays. it doesnt take a profound leap in logic that the optimizer may have unfolded everything and realized certain code was not going to change the state of the program, thus removed it. Maybe it didnt, but then again maybe it did.
- hyperpape 9y ago
  > information is information It's information, but not worthwhile information. > It doesnt take a profound leap in logic that the optimizer may have unfolded everything and realized certain code was not going to change the state of the program, thus removed it. Maybe it didnt, but then again maybe it did. Prove it. This article has had a ton of traffic. If you see the thing that everyone missed, a lot of people will be very impressed with you.
- Ultimatt 9y ago
  Did you try with an actual array or a Python list? https://docs.python.org/3/library/array.html https://docs.python.org/3/library/array.html or numpy you might be able to recover the same effect. Your average line of Python is miles away from low level and simple operations. Pretty much any dynamic language with a large runtime is. Especially when they default to lists not arrays. You should see your result as evidence of that. Not assume this discussion is flawed.

corysama 9y ago

I'm surprised you got such a high (11%) boost. I would not expect branch prediction issues from your code to have much of an effect in Python because the Python interpreter itself naturally introduces 10x as many branches under the hood as the code it interprets.

winstonewert 9y ago
guess: the branches in the python VM are more accurately predicted than branch on the data. The data is going to be random and thus unpredictable, but the branches in the VM are probably pretty predictable.
- dom0 9y ago
  Python if statements will branch on very few processor instructions in the VM; so I don't think branch prediction of the processor is able to predict different Python if's — they're all the same to it. Well, that... and even simple Python VM instructions tend to take dozens of insns to execute.