Hi Robert Paprocki, (Sorry I didn't get your email. So lua-l gets to be the transition medium :) Here is a messy proof-of-concept for handling IP addresses matching a set of CIDRs at large scale. As we talked about, it works by constructing a tree of CIDRs as an array and matching IP addresses against it. (Note: the array is static size and holds the entire 32bit ip address space as a 2GB array. However, this malloc'd memory is mostly unused and due to memory overcommit in Linux, the actual memory of your RSS is much less.) I was able to achieve the following numbers for insertion (which includes significant time spent creating IP addresses via math.random): pdonnell@icewind ~/Downloads/LuaJIT-2.1.0-beta3/src$ ./luajit ~/cidr-match.lua CIDRs inserted per second (100000): 986747 IPv4 addr searched per second (100000): 838272 CIDRs inserted per second (1e+06): 2723912 IPv4 addr searched per second (1e+06): 2027817 CIDRs inserted per second (1e+07): 2589888 IPv4 addr searched per second (1e+07): 1621741 pdonnell@icewind ~/Downloads/LuaJIT-2.1.0-beta3/src$ luajit ~/cidr-match.lua CIDRs inserted per second (100000): 278164 IPv4 addr searched per second (100000): 154175 CIDRs inserted per second (1e+06): 336277 IPv4 addr searched per second (1e+06): 193654 CIDRs inserted per second (1e+07): 223287 IPv4 addr searched per second (1e+07): 117337 (For some reason, luajit 2.0 -- the second run above -- is much slower than 2.1.) Here's the memory usage with 1 million CIDRs: $ ./luajit ~/cidr-match.lua VmPeak: 2109684 kB VmSize: 2109684 kB VmLck: 0 kB VmPin: 0 kB VmHWM: 683128 kB VmRSS: 683128 kB VmData: 2097480 kB VmStk: 132 kB VmExe: 480 kB VmLib: 3364 kB VmPTE: 1384 kB VmPMD: 28 kB VmSwap: 0 kB Note the important bit there VmRSS which indicates it's actually using 680MB for 1 million CIDRs... so not quite that small :). Memory use for normal use-cases may be very different. The code is rough and doesn't handle network byte order correctly but that should be easy enough to fix. Exercise for the reader and all that. Thanks for the fun programming challenge and thanks to Kong for hosting the Lua workshop! -- Patrick Donnelly
Attachment:
cidr-match.lua
Description: Binary data