5 ms·

IME CPU caches can be observed in almost all languages, regardless of how detached they are from the machine. What I'm really wondering is, if branch prediction

• stingraycharles 2y ago
  It should be, as most interpreted code uses a JIT native compiler at this point, which implies the branch prediction is native as well. I would be happy to stand corrected if someone knows more about this, though!
  • tarruda 2y ago
    AFAIK CPython doesn't JIT compile.
    • pansa2 2y ago
      Recent versions of CPython do have an experimental JIT compiler. I'm not sure how widely-used it is, though. https://peps.python.org/pep-0744/ https://peps.python.org/pep-0744/
      • Qem 2y ago
        It's disabled by default, not production ready. You need to compile CPython yourself if you want to try it.
  • pansa2 2y ago
    > most interpreted code uses a JIT native compiler at this point I suspect most JavaScript code is JIT-compiled - but most Python, Ruby etc is interpreted (via bytecode).
• vlovich123 2y ago
  Why would you think that branch prediction wouldn’t be? Do you think the interpreter is adding too much false sharing to the branch predictor to render it worthless?
  • almostgotcaught 2y ago
    you do realize that the Python if x > 128: r = not r doesn't necessarily correspond to one branch at the ASM instruction level right? in fact, a priori, it doesn't even correspond to absolutely any branches at the ASM instruction level.
    • vlovich123 2y ago
      Yes I do and that’s neither here nor there. There almost certainly ASM instruction level branches to implement the conditional and the branch predictor isn’t tied to a single instruction - the rough high level mental model is a cache of a few of the least significant digits of the CPU to the prediction although in practice it’s far more complicated. Since the predictor is right like 80% of the time, it means that even when there’s false sharing of a lot of branches, the CPU does a good job predicting. It’s performance is primarily impacted when execution takes both branches closer to 50/50 than to 100/0. That’s why I asked about false sharing specifically as that’s the main way I can think of that Python code wouldn’t be able to observe the branch predictor performance - because the interpreter has so many branches internally that it dominates any branches that might be caused by the Python code itself.
    • exyi 2y ago
      It corresponds to a way more than one branch at instruction level. The branch prediction AFAIK does not care based on what are you branching, it just assumes branches will go in similar sequences as they did last time. If the Python 'if' is never taken, the instruction-level predictor will learn that after the comparison operation, there is an 'if' operation and then another array access operation. If the Python 'if' is unpredictable unpredictable, CPU predictor can't be sure which opcode are we processing after 'if', so there will be penalty.
      • mardifoufs 2y ago
        Is there any public documentation on modern branch prediction algorithms? I know branch prediction is very important to modern CPU so SOTA techniques are probably not public... But it's really amazing what it can do especially considering the "limited" cache sizes that branch predictors have .
• exyi 2y ago
  It is! Although my test case is probably an unrealistically bad scenario: It's the classic, why is processing sorted array faster than unsorted one def f(arr): r = True for x in arr: if x > 128: r = not r return r arr = [ random.randint(0, 255) for i in range(0, 1000_000) ] arr_sorted = list(sorted(arr)) %timeit f(arr) %timeit f(arr_sorted) Results are (on my machine): 17.5 ms for unsorted, and 13.5 ms for sorted. For comparison, in a compiled language, the difference is 4x
  • ammar2 2y ago
    Edit: Analyzed the wrong thing earlier. This depends on the Python version, but if it has the specializing interpreter changes, the `COMPARE_OP` comparing the integers there is probably hitting a specialized `_COMPARE_OP_INT` [1]. This specialization has a ternary that does `res = (sign_ish & oparg) ? PyStackRef_True : PyStackRef_False;`. This might be the branch that ends up getting predicted correctly? Older versions of Python go through a bunch of dynamic dispatch first and then end up with a similar sort of int comparison in `long_richcompare`. [2] [1] https://github.com/python/cpython/blob/561965fa5c8314dee5b86586ffa16c1f369d1fa2/Python/bytecodes.c#L2614-L2633 https://github.com/python/cpython/blob/561965fa5c8314dee5b86... [2] https://github.com/python/cpython/blob/561965fa5c8314dee5b86586ffa16c1f369d1fa2/Objects/longobject.c#L3590-L3592 https://github.com/python/cpython/blob/561965fa5c8314dee5b86...
    • dzaima 2y ago
      This isn't actually timing the sorting, but just the (dumb) function f.
      • ammar2 2y ago
        Oh whoops, that's right. I totally missed that.
  • GBhpkmY 2y ago
    [dead]
  • 2y ago
• eulgro 2y ago
  My guess would be that branch misprediction does have an impact on interpreted language, but much less. If bytecode instructions take on average 20 CPU cycles to execute, and the branch misprediction penalty is 50 CPU cycles, the relative cost of a misprediction is much smaller than in compiled code.
  • adgjlsfhk1 2y ago
    the counterpoint is that a lot of those 20 instructions are also branches
• saagarjha 2y ago
  Yep, this is why Spectre mitigations are applied to browsers.