J. Gareth Moreton

2018-08-03 19:57:14 UTC

Hi everyone,

So I'm pondering about attempting to implement the binary search system I

devised for case blocks.Â To find the correct case label, you need to

iterate a search loop a fixed maximum of ceil(log2(n)) times, where n is

the number of individual case values (excluding "else").Â Given that this

is quite a low number and I managed to get the loop itself down to just 8

instructions (not including the comparison and conditional jump at the

end), this could be unwrapped for low values of ceil(log2(n))... possibly

up to 7 or 8, I'd say.Â However, if an exact match is found early, how

serious is the penalty of having a conditional jump forward on each

unrolled iteration for x86-64, whether it's taken or not? (This would be

the equivalent of a Break command)

Gareth aka. Kit

So I'm pondering about attempting to implement the binary search system I

devised for case blocks.Â To find the correct case label, you need to

iterate a search loop a fixed maximum of ceil(log2(n)) times, where n is

the number of individual case values (excluding "else").Â Given that this

is quite a low number and I managed to get the loop itself down to just 8

instructions (not including the comparison and conditional jump at the

end), this could be unwrapped for low values of ceil(log2(n))... possibly

up to 7 or 8, I'd say.Â However, if an exact match is found early, how

serious is the penalty of having a conditional jump forward on each

unrolled iteration for x86-64, whether it's taken or not? (This would be

the equivalent of a Break command)

Gareth aka. Kit