[fpc-devel] Optimization theory

[J. Gareth Moreton]

 One other problem with this method, and I think it has caused problems
before - https://bugs.freepascal.org/view.php?id=32079 - is what happens if
an invalid value is passed in for the opcode.  Granted, a sanity check can
be employed.
 One would need to develop some tight timing tests to determine the fastest
method for a given number of cases.  As Florian once stated... it takes a
large number of jumps before the standard linear subtraction search (where
the ordinal difference is subtracted from each case branch in turn) becomes
prohibitive.  On modern processors it can be as high as 64.

 Gareth aka. Kit

 On Mon 25/06/18 11:18 , Martin fpc at mfriebe.de sent:
    On 25/06/2018 05:23, J. Gareth Moreton wrote:
   Actually you're right - that is the fastest method (it's written O(1),
by the way, if it doesn't depend on n).  The drawback is that the large
majority of instructions don't have such an optimisation procedure, so the
table  would be extremely sparse.  There are 1,109 individual
instructions on x86 that FPC currently supports.  Come to think of it,
even that is not too bad as far as memory goes - you're looking at 8,872
bytes on i386 (4 bytes for the instruction and 4 bytes for a pointer) and
17,744 bytes on x86-64 (8 bytes for each field), both are potentially
cacheable on the CPU hence won't be too costly in regards to looking it
up.  Not sure why I overlooked that one.  Thanks Martin.

 While probably not worth it, but if you want to save memory (and only few
entries have data): Use 2 maps:

 map1: array[opcode] of byte; // I do not know how efficient reading bytes
is....
       maps the (hopefully fewer than 255 active entries)

 map2: array[byte] of codepointer

 _______________________________________________
 fpc-devel maillist - fpc-devel at 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 at lists.freepascal.org
[2] http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.freepascal.org/pipermail/fpc-devel/attachments/20180625/670af805/attachment.html>