Bug #17387: Speed up Proxy::DHCP::SubnetService#find_subnet - Smart Proxy - Foreman

Bug #17387

Speed up Proxy::DHCP::SubnetService#find_subnet

Added by Dmitri Dolguikh almost 6 years ago. Updated about 4 years ago.

Status:

Closed

Priority:

Normal

Assignee:

Dominic Cleal

Category:

DHCP

Target version:

1.13.2

Difficulty:

Triaged:

Bugzilla link:

Pull request:

https://github.com/theforeman/smart-proxy/pull/477, https://github.com/theforeman/smart-proxy/pull/476

Fixed in Releases:

Found in Releases:

Description

Current implementation is O(n), it can be made O(log n).

Related issues

Associated revisions

Revision c16b176d (diff)
Added by Dominic Cleal over 5 years ago

fixes #17387 - SubnetService#find_subnet has constant time lookup

find_subnet is now approximately constant with the number of subnets
configured, using hash lookups of possible network prefixes for the
given IP address until the most specific prefix is found. Benchmark
results:

find_subnet (1 subnets, 200 hosts)
                              1.665k (± 9.5%) i/s -     16.437k in   9.991955s
    find_subnet (5 subnets, 1000 hosts)
                            331.898  (± 7.5%) i/s -      3.298k in   9.999109s
    find_subnet (50 subnets, 10000 hosts)
                             31.363  (± 6.4%) i/s -    313.000  in  10.005986s
    find_subnet (500 subnets, 100000 hosts)
                              3.078  (± 0.0%) i/s -     31.000  in  10.072384s
    find_subnet (5000 subnets, 1000000 hosts)
                              0.301  (± 0.0%) i/s -      4.000  in  13.298996s

add_subnet only checks for an identical network prefix instead of
overlapping prefixes with #find_subnet, speeding it up considerably.
Benchmark results:

add_subnet (1)     41.389k (±17.4%) i/s -    378.638k in   9.792687s
        add_subnet (5)     10.278k (±11.2%) i/s -     99.588k in   9.931308s
       add_subnet (50)      1.062k (± 9.3%) i/s -     10.470k in   9.991114s
      add_subnet (500)    105.161  (± 9.5%) i/s -      1.042k in  10.007969s
     add_subnet (1000)     53.826  (± 7.4%) i/s -    536.000  in  10.012055s
    add_subnet (15000)      3.424  (± 0.0%) i/s -     35.000  in  10.241879s