Bug #17387

Speed up Proxy::DHCP::SubnetService#find_subnet

Added by Dmitri Dolguikh 4 months ago. Updated 4 months ago.

Status:Closed
Priority:Normal
Assigned To:Dominic Cleal
Category:DHCP
Target version:-
Difficulty: Bugzilla link:
Found in release: Pull request:https://github.com/theforeman/smart-proxy/pull/477, https://github.com/theforeman/smart-proxy/pull/476
Story points-
Velocity based estimate-
Release1.13.2Release relationshipAuto

Description

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


Related issues

Related to Smart Proxy - Bug #17373: ISC dhcp provider is unable to handle very big networks New 11/17/2016

Associated revisions

Revision c16b176d
Added by Dominic Cleal 4 months 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

History

#1 Updated by Dmitri Dolguikh 4 months ago

  • Related to Bug #17373: ISC dhcp provider is unable to handle very big networks added

#2 Updated by The Foreman Bot 4 months ago

  • Status changed from Assigned to Ready For Testing
  • Pull request https://github.com/theforeman/smart-proxy/pull/476 added

#3 Updated by The Foreman Bot 4 months ago

  • Pull request https://github.com/theforeman/smart-proxy/pull/477 added

#4 Updated by Dominic Cleal 4 months ago

  • Status changed from Ready For Testing to Closed
  • % Done changed from 0 to 100

#5 Updated by Dominic Cleal 4 months ago

  • Assigned To changed from Dmitri Dolguikh to Dominic Cleal
  • Release set to 1.13.2

Also available in: Atom PDF