For that very reason, I put an upper limit of 2,048 on the jump table size
(which results in an 8 KiB table), although it was modified later so this
bound doesn't apply if every single label points to a single value and more
or less forms a continuum (e.g, you have 2,500 labels and none of them are
a range).
For a linear search, each branch takes between 2 and 4 instructions to
test, if I remember correctly, although there is a lot of dependency, since
it usually involves a subtraction followed by a conditional jump. My
additional changes over at #34859 introduce some extra conditional jumps to
break out sooner once the program knows there won't be a match (because,
for example, there are labels for just 1 and 3 and the input value is 2).
Before, the flow only jumped out if it reached a range and the input was
less than the lower bound. I did some preliminary testing with
tests/bench/bcase.pp and the overall timespan is about 5% faster.
Gareth aka. Kit
On Tue 15/01/19 17:27 , Martok list...@martoks-place.de sent:
Am 14.01.2019 um 15:01 schrieb J. Gareth Moreton:
> Martok mentioned doing some checks differently in the bug report in
question,
> such as 6 comparisons being faster than a jump table. Are there any
others
> worth mentioning?
Not neccessarily faster, but in that code definitely smaller. Is there a
way to
directly estimate how large the generated code might be, maybe something
like
"numlabels*constant"?
For the "faster" question, the cache line occupation matters more than
instruction throughput. If your jumptable gets large enough to force a
full data
cache line flush, you could have done a lot of instructions in the time
the CPU
waits for the data. And I haven't found reliable information how the
Spectre-related microcode updates changed that, given that both cmp/jmp
and
jmp[indirect] used to be heavily optimized, but were both affected.
--
Regards,
Martok
___
fpc-devel maillist - fpc-devel@lists.freepascal.org [1]
http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel
[2]">http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel
Links:
--
[1] mailto:fpc-devel@lists.freepascal.org
[2] http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel
___
fpc-devel maillist - fpc-devel@lists.freepascal.org
http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel
