4 ms·

>To achieve high performance, APISIX stores the list of IP addresses in a hash table and uses it for matching (O(1)) than iterating through the list (O(N)). Fo

>To achieve high performance, APISIX stores the list of IP addresses in a hash table and uses it for matching (O(1)) than iterating through the list (O(N)). For IP allow/deny lists, unless the list were very large, I imagine it would be faster on most hardware to use an array than a map due to LX caches. It would have been cool to see an adaptive approach based on the size (e.g. for values of N over X, we use a map, otherwise an array). Maybe these lists are much larger in production than my assumptions about their size.

rewmie 3y ago
> I imagine it would be faster on most hardware to use an array than a map due to LX caches. I didn't understood your point. I mean, a hash map is basically an array whose index is calculated from a key.
- collinvandyck76 3y ago
  Those arrays usually contain pointers to other data structures, allocated on the heap in different places, which often results in a cache miss / cpu stall. It's still a constant time lookup, but for small values of N, avoiding the cache misses is often faster, even with an O(N) algorithm.
  - arp242 3y ago
    Also you do need to calculate that hash key, which isn't free either. I generally found that lookups in lists are faster than hashmaps for sizes smaller than about 10 or so, but details may vary on the exact implementation etc.
    - seanhunter 3y ago
      This is the origin of the famous quote from Rob Pike which goes something like "Simple data structures are better when n is small and n is almost always small". It hasn't aged as well as he might have liked, given that sometimes n gets really really big now, but the point still holds- in lots of common use cases simple algorithms with low constant factors dominate fancy algorithms with theoretically better O() up to a certain threshold data scale. In this case it would presumably be up to a certain number of routes and/or ip addresses.

rewmie 3y ago

> I imagine it would be faster on most hardware to use an array than a map due to LX caches. I didn't understood your point. I mean, a hash map is basically an array whose index is calculated from a key.

collinvandyck76 3y ago
Those arrays usually contain pointers to other data structures, allocated on the heap in different places, which often results in a cache miss / cpu stall. It's still a constant time lookup, but for small values of N, avoiding the cache misses is often faster, even with an O(N) algorithm.
- arp242 3y ago
  Also you do need to calculate that hash key, which isn't free either. I generally found that lookups in lists are faster than hashmaps for sizes smaller than about 10 or so, but details may vary on the exact implementation etc.
  - seanhunter 3y ago
    This is the origin of the famous quote from Rob Pike which goes something like "Simple data structures are better when n is small and n is almost always small". It hasn't aged as well as he might have liked, given that sometimes n gets really really big now, but the point still holds- in lots of common use cases simple algorithms with low constant factors dominate fancy algorithms with theoretically better O() up to a certain threshold data scale. In this case it would presumably be up to a certain number of routes and/or ip addresses.