Skip to content
  • Thomas Haller's avatar
    keyfile: optimize parsing of addresses/routes in keyfile reader · 584a06e4
    Thomas Haller authored
    With this, parsing the properties address/route (for both IPv4/IPv6)
    has a runtime complexity of O(n*ln(n)).
    
    Previously, parsing these properties was O(1), but the constant factor
    was very high because for each address/route x ipv4/ipv6 combination we would
    search about 2*1001 times whether there is a matching value.
    Now the runtime complexity is O(n*ln(n)) for each of these 4 properties
    where n is the number of entries in the keyfile.
    
    Also note, that we only have 4 properties for which the parsing has
    this complexity. Hence, parsing the entire keyfile is still O(n) + 4*O(n*ln(n))
    which reduces to O(n*ln(n)). So, parsing the entire keyfile is still benign
    and the logarithmic factor comes merely from sorting (which is fast).
    
    Now, the number of supported addresses/routes is no longer limited
    to 1000 (as before). Now we would accept all keys up from 0 up to
    G_MAXINT32.
    
    Like before, indexes will be automatically adjusted and gaps in the
    numbering are accepted. That is convenient, if the user edits the
    keyfile manually and deletes some lines. And we anyway must not change
    behavior.
    
      $ multitime -n 200 -s 0 -q ./src/settings/plugins/keyfile/tests/test-keyfile
      # build with -O2 --without-more-asserts
      # before:
                    Mean                Std.Dev.    Min         Median      Max
        real        0.290+/-0.0000      0.013       0.275       0.289       0.418
        user        0.284+/-0.0000      0.010       0.267       0.284       0.331
      # after:
                    Mean                Std.Dev.    Min         Median      Max
        real        0.101+/-0.0000      0.002       0.099       0.100       0.118
        user        0.096+/-0.0000      0.003       0.091       0.096       0.113
        sys         0.004+/-0.0000      0.002       0.001       0.004       0.009
    584a06e4