OPTIMISATION.txt

   1 This document describes configuration options which may help one to generate onions faster.
   2 First of all, default configuration options are tuned for portability, not performance.
   3 User is expected to pick optimal settings depending on hardware mkp224o will run on and ammount of filters.
   4
   5
   6 ED25519 implementations:
   7 mkp224o includes multiple implementations of ed25519 code, tuned for different processors.
   8 Default is ref10 implementation from SUPERCOP, which is suboptimal in many cases.
   9 Implementation is selected at configuration time, when running `./configure` script.
  10 If one already configured/compiled code and wants to change options, just re-run
  11 `./configure` and also run `make clean` to clear compiled files, if any.
  12 At the time of writing, these implementations are present:
  13 +----------------+-----------------------+-------------------------------------------------+
  14 | implementation | enable flag           | notes                                           |
  15 |----------------+-----------------------+-------------------------------------------------+
  16 | ref10          | --enable-ref10        | SUPERCOP' ref10, pure C, very portable, default |
  17 | amd64-51-30k   | --enable-amd64-51-30k | SUPERCOP' amd64-51-30k, amd64 assembler,        |
  18 |                |                       | only works in x86_64 architecture               |
  19 | amd64-64-24k   | --enable-amd64-64-24k | SUPERCOP' amd64-64-24k, amd64 assembler,        |
  20 |                |                       | only works in x86_64 architecture               |
  21 | ed25519-donna  | --enable-donna        | portable, based on amd64-51-30k, but C, not asm |
  22 | ed25519-donna  | --enable-donna-sse2   | uses SSE2, needs x86 architecture               |
  23 +----------------+-----------------------+-------------------------------------------------+
  24 When to use what:
  25  - on 32-bit x86 architecture "--enable-donna" will probably be fastest, but one should try
  26    using "--enable-donna-sse2" too
  27  - on 64-bit x86 architecture, it really depends on your processor; "--enable-amd64-51-30k"
  28    worked best for me, but you should really benchmark on your own machine
  29  - on ARM "--enable-donna" will probably work best
  30  - otherwise you should benchmark, but "--enable-donna" will probably win
  31
  32 Please note, that these recomendations may become out of date if more implementations
  33 are added in the future; use `./configure --help` to obtain all available options.
  34 When in doubt, benchmark.
  35
  36
  37 Onion filtering settings:
  38 mkp224o supports multiple algorithms and data types for filtering.
  39 Depending on your use case, picking right settings may increase performance.
  40 At the time of writing, mkp224o supports 2 algorithms for filter searching:
  41 sequential and binary search. Sequential search is default, and will probably
  42 be faster with small ammount of filters. If you have lots of filters (lets say >100),
  43 then picking binary search algorithm is the right way.
  44 mkp224o also supports multiple filter types: filters can be represented as integers
  45 instead of being binary strings, and that can allow better compiler's optimizations
  46 and faster code (dealing with fixed-size integers instead of variable-length strings is simpler).
  47 On the other hand, fixed size integers limit length of filters, therefore
  48 binary strings are used by default.
  49
  50 Current options, at the time of writing:
  51   --enable-binsearch      enable binary search algoritm; MUCH faster if there
  52                           are a lot of filters. by default, if this isn't enabled,
  53                           sequential search is used
  54
  55   --enable-intfilter[=(32|64|128|native)]
  56                           use integers of specific size (in bits) [default=64]
  57                           for filtering. faster but limits filter length to:
  58                           6 for 32-bit, 12 for 64-bit, 24 for 128-bit. by default,
  59                           if this option is not enabled, binary strings are used,
  60                           which are slower, but not limited in length.
  61
  62   --enable-binfilterlen=VAL
  63                           set binary string filter length (if you don't use intfilter).
  64                           default is 32 (bytes), which is maximum key length.
  65                           this may be useful for decreasing memory usage if you
  66                           have a lot of short filters, but then using intfilter
  67                           may be better idea.
  68
  69   --enable-besort         force intfilter binsearch case to use big endian
  70                           sorting and not omit masks from filters; useful if
  71                           your filters aren't of same length.
  72                           let me elaborate on this one.
  73                           by default, when binary search algorithm is used with integer
  74                           filters, we actually omit filter masks and use global mask variable,
  75                           because otherwise we couldn't reliably use integer comparision operations
  76                           combined with per-filter masks, as sorting order there is unclear.
  77                           this is because majority of processors we work with are little-endian.
  78                           therefore, to achieve proper filtering in case where filters
  79                           aren't of same length, we flatten them by inserting more filters.
  80                           binary searching should balance increased overhead here to some extent,
  81                           but this is definitelly not optimal and can bloat filtering table
  82                           very heavily in some cases (for example if there exists say 1-char filter
  83                           and 8-char filter, it will try to flatten 1-char filterto 8 chars
  84                           and add 32*32*32*32*32*32*32 filters to table which isn't really good).
  85                           this option makes us use big-endian way of integer comparision, which isn't
  86                           native for current little-endian processors but should still work much better
  87                           than binary strings. we also then are able to have proper per-filter masks,
  88                           and don't do stupid flattening tricks which may backfire.
  89
  90                           TL;DR: its quite good idea to use this if you do "--enable-binsearch --enable-intfilter"
  91                           and have some random filters which may have different length.
  92
  93
  94 Benchmarking:
  95 It's always good idea to see if your settings give you desired effect.
  96 There currently isn't any automated way to benchmark different configuration options, but it's pretty simple to do by hand.
  97 For example:
  98 # prepare configuration script
  99 ./autogen.sh
 100 # try default configuration
 101 ./configure
 102 # compile
 103 make
 104 # benchmark implementation speed
 105 ./mkp224o -s -d res1 neko
 106 # wait for a while, copy statistics to some text editor
 107 ^C # stop experiment when you've collected enough data
 108 # try with different settings now
 109 ./configure --enable-amd64-64-24k --enable-intfilter
 110 # clean old compiled files
 111 make clean
 112 # recompile
 113 make
 114 # benchmark again
 115 ./mkp224o -s -d res2 neko
 116 # wait for a while, copy statistics to some text editor
 117 ^C # stop experiment when you've collected enough data
 118 # configure again, make clean, make, run test again.......
 119 # until you've got enough data to make decisions
 120
 121 when benchmarking filtering settings, remember to actually use filter files you're going to work with.
 122
 123
 124 What options I use:
 125 For my lappy with old-ish i5 I do `./configure --enable-amd64-51-30k --enable-intfilter` incase I want single onion,
 126 and `./configure --enable-amd64-51-30k --enable-intfilter --enable-binsearch --enable-besort` when playing with dictionaries.
 127 For my raspberry pi 2, `./configure --enable-donna --enable-intfilter`
 128 (and also +=" --enable-binsearch --enable-besort" for dictionaries).