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

Reply via email to