And even in that case I doubt it's worse, because what you mentioned, branch prediction, actually helps binary search more, not goes against it.

If we were going to build a test program, what would that look like?

Furs wrote:

Furs wrote:

... always use binary search.

But it takes way less branches so it's far easier to predict?

Here's a simple task for you to think about. Given 2 identical glass balls and a skyscraper on N floors. It is known for sure that the ball definitely breaks when thrown from the last floor, and also that both balls break when thrown from the same floor. Find the minimum floor for the minimum number of throws from which the ball will break when thrown?

Solving this problem, it may become clear to you why C/Pascal compilers do not generate a large number of jumps by creating a binary tree when generating a switch/case.

Furs wrote:

And even in that case I doubt it's worse, because what you mentioned, branch prediction, actually helps binary search more, not goes against it.

You can't know that unless you also know the data pattern.

If the pattern is pathological it can make all predictions be wrong and make your code worse.

Like I said, there is no way to know without testing it. You can't look at these thing statically and "know" it is better.

if(some_boolean_var && some_expensive_function())    

if(some_expensive_function() && some_boolean_var)    

The data pattern is irrelevant ...

I wish it was as "obvious" as you seems to suggest. You claimed "always use binary search. It's objectively better unless you have less than 4 entries.". It isn't obvious to me how you can know that, when you don't know the data patterns, and you don't know the misprediction penalty.

A single misprediction penalty can easily eat up the time of four correctly predicted cmp instructions (more actually) in all CPUs that I am aware of. So your claim of 4 entries being enough to "obviously" be better than everything else is not obvious to me in any way.

;to assemble: "fasm -d TEST=uselss_cmp_chain"
;to assemble: "fasm -d TEST=objectivy_better_binary"

macro uselss_cmp_chain {
        cmp     al,1
        jz      item1
        cmp     al,2
        jz      item2
        cmp     al,3
        jz      item3
        cmp     al,4
        jz      item4
}

macro objectivy_better_binary {
        cmp     al,2
        ja      high_half
        jb      item1
        jmp     item2
high_half:
        cmp     al,3
        je      item3
        jmp     item4
}

format elf executable

SYS_EXIT        = 1

        mov     ecx,1000000
outer_loop:
        mov     ebx,the_data_pattern_is_unimportant_len
        mov     esi,the_data_pattern_is_unimportant
inner_loop:
        lodsb
        match x,TEST {x}
next_item:
        dec     ebx
        jnz     inner_loop
        loop    outer_loop
        mov     eax,SYS_EXIT
        int     0x80

item1:  jmp     next_item
item2:  jmp     next_item
item3:  jmp     next_item
item4:  jmp     next_item

the_data_pattern_is_unimportant:
        while % <= 1000
                db 1
        end while
        db 2,3,4
the_data_pattern_is_unimportant_len = $ - the_data_pattern_is_unimportant    

~ fasm -d TEST=uselss_cmp_chain test.asm && time ./test
flat assembler  version 1.73.08  (4029940 kilobytes memory)
2 passes, 1139 bytes.

real    0m4.510s
user    0m4.464s
sys     0m0.000s
~ fasm -d TEST=objectivy_better_binary test.asm && time ./test
flat assembler  version 1.73.08  (4041296 kilobytes memory)
2 passes, 1137 bytes.

real    0m5.159s
user    0m5.108s
sys     0m0.000s    

the_data_pattern_is_unimportant:
        while % <= 1000
                db 4
        end while
        db 2,3,1
the_data_pattern_is_unimportant_len = $ - the_data_pattern_is_unimportant    

~ fasm -d TEST=uselss_cmp_chain test.asm && time ./test
flat assembler  version 1.73.08  (4043436 kilobytes memory)
2 passes, 1139 bytes.

real    0m6.561s
user    0m6.528s
sys     0m0.004s
~ fasm -d TEST=objectivy_better_binary test.asm && time ./test
flat assembler  version 1.73.08  (4027244 kilobytes memory)
2 passes, 1137 bytes.

real    0m7.789s
user    0m7.652s
sys     0m0.000s    

You don't freaking need to test what's obvious.

I'm still not seeing the obvious here.

Code:

macro uselss_cmp_chain {
        cmp     al,1
        jz      item1
        cmp     al,2
        jz      item2
        cmp     al,3
        jz      item3
        cmp     al,4
        jz      item4
}

macro objectivy_better_binary {
        cmp     al,2
        ja      high_half
        jb      item1
        jmp     item2
high_half:
        cmp     al,3
        je      item3
        jmp     item4
}    

; assume AL is in range 1-4
        cmp     al,3
        ja      item4
        je      item3
        jpe     item2
        jmp     item1    

hack_1234_chain_1 {
sub al,3 ;add al,-3
jz item3
jp item2
js item1
jmp item4 }

hack_1234_chain_2 {
add al,-3
jz item3
jp item2
ja item1
jmp item4 }

hack_1234_chain_3 {
sub al,3
jz item3
jp item2
jb item1
jmp item4 }