I'm trying to speed up a Python script that reads a large log file (JSON lines, 50gb+) and filter out results that match 1 of 2000 CIDR ranges.Logfile20 million lines{ip:xxx.xxx.xxx.xxx,timestamp:2017-05-27T04:00:35-04:00,data:{},error:EOF,error_component:banner}{ip:xxx.xxx.xxx.xxx,timestamp:2017-05-27T04:00:35-04:00,data:{banner:xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx,ehlo:xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx,starttls:500 Unknown command\r\n},error:Bad return code for STARTTLS,error_component:starttls}{ip:xxx.xxx.xxx.xxx,timestamp:2017-05-27T04:00:35-04:00,data:{},error:EOF,error_component:banner}{ip:xxx.xxx.xxx.xxx,timestamp:2017-05-27T04:00:35-04:00,data:{banner:xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx,ehlo:xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx,starttls:502 No such command\r\n},error:Bad return code for STARTTLS,error_component:starttls}CIDR file2,000 lines86.80.0.0/1277.160.0.0/12188.200.0.0/13178.224.0.0/1384.24.0.0/13Scriptimport sysimport jsonfrom netaddr import *reload(sys)sys.setdefaultencoding('utf-8')filename = 'results.json'filename = unicode(filename, 'utf-8')cidr_filename = 'cidr.txt'rowcount = 0count = 0# Load CIDR rangeswith open(cidr_filename, 'r') as f:    cidr = [line.strip() for line in f]# Load JSON line by linewith open(filename) as f:    for line in f:        output = json.loads(line)        rowcount += 1        # Match if IP is in CIDR ranges        if all_matching_cidrs(output['ip'], cidr):            if 'banner' in output['data']:                print(output['ip'] + '\t' + output['data']['banner'])                count += 1print('---------------------------------------')print('LINES:   {rowcount}')print('RESULTS: {count}')print('---------------------------------------')Current resultsParsing an example set of 100,000 rows takes now 8 minutes using:PypyMacBook Pro with 2.8 GHz Intel Core i7, 16Gb RAM, SSDParsing the complete set of 20,000,000 rows would take a staggering 26 hours. ---------------------------------------LINES:   100000RESULTS: 1243---------------------------------------real    7m57.739suser    7m52.127ssys     0m4.177sThe bottleneck is the number of CIDR ranges to search within, when I run an example set of 100,000 row against 1 CIDR range it takes only 1.2 seconds.---------------------------------------LINES:   100000RESULTS: 4---------------------------------------real    0m1.201suser    0m1.095ssys     0m0.090sIs there a faster way of accomplishing this? Would Multithreading/Multiprocessing speed things up? Any help or other feedback would be much appreciated!Things I've done:Using Pypy, this is 9x(!) faster than Python 2.7 for this job.Tried using Tim Bray's Widefinder but couldn't make it work as it focuses on regex searches IMHO.UPDATErolfl's solution brought my times to parse 20,344,457 rows from 26 hours to 4.5 minutes!---------------------------------------LINES:   20344457RESULTS: 130863---------------------------------------real    4m27.661s user    3m55.171s sys     0m26.793sTemporalWolf's advice to cProfile my code showed that indeed json.loads() was a bottleneck:ncalls    tottime  percall  cumtime  percall filename:lineno(function)16607394  131.960    0.000  131.960    0.000 {_pypyjson.loads}Following his advice to slice the IP address natively instead of loading each line as JSON it was 2.5x times faster!---------------------------------------LINES:   20344457RESULTS: 130863---------------------------------------real    1m40.548suser    1m13.885ssys     0m22.664s
Filtering a large (50gb+) JSON lines file matching CIDR's
python;performance;parsing;json;ip address
Is there a faster way of accomplishing this? Would Multithreading/Multiprocessing speed things up? Any help or other feedback would be much appreciated!No, for the most part, multi-threading will make no difference for you. At some point the bottleneck should be the IO speed of reading 50GB of file content, and not the speed of the processing. You also need to read the file sequentially (I presume) to get the output in the same order as the input.But, fundamentally, the solution should not need to have multi-threaded execution in order to improve the performance.Learning how to measure performance of various parts of your code is an important skill. For the moment, it may be as simple as timing this code:# Load JSON line by linewith open(filename) as f:    for line in f:        output = json.loads(line)        rowcount+=1i.e. convert each line from JSON, and count the lines.... how fast is that? I would expect that the whole program should be just as fast when the IP CIDR lookups work fast too.Your performance issue is almost certainly related to this line here:if all_matching_cidrs(output['ip'], cidr):Your timings already support this.... it takes 1 second to search all records in 1 CIRD, but significantly longer for 2000 CIDRs...So, you have a performance problem in the order of \$O(mn)\$ where \$m\$ is the number of rows in the file, and \$n\$ is the number of CIDRs.You can't improve the performance related to the number of rows in the files, but you can improve the cost of the CIDR lookups. What if it was a fixed-cost to check all CIDR matches? Then your overall performance becomes \$O(m)\$ and does not depend on the number of CIDR records.You can do this by preprocessing the CIDR data in to a structure that allows a fixed-cost lookup.The structure I would use is a binary tree consisting of nodes representing each bit in the CIDR specs. Each leaf node represents a CIDR to include. I.e. you preprocess the CIDRs in to the tree that at most has 32 levels (for a /32 CIDR).Then, for the lookup, you take your IP from the JSON, convert it in to an integer, and start shifting bits from the most significant. For each bit, you start descending the CIDR tree, and if you can descend the tree until you hit a leaf node, then you have found a matching CIDR. At most, this will be 32 iterations down the tree, but for the most part, CIDR's seldom are that specific. So, let's assume at most a /24 CIDR, meaning that you reduce your lookups to at most 24 descents, instead of as many as 2000 complete checks.It comes down to the algorithm.Update - example lookupNote, I hacked together this tree for supporting faster lookups of IPs in a number of CIDR ranges. Python is not my primary language, so inspect it carefully, and adjust as needed. Specifically, I have used some naive mecheanisms for parsing IP addresses in to integers. Use dedicated libraries to do that instead.You can see it running on ideone: https://ideone.com/cd0O2Idef parseIPPart(ipx, shift):    try:        return int(ipx) << shift    except TypeError:        return 0def parseIP(ipString):    ips_shifts = zip(ipString.split(.), range(24, -1, -8))    addr = [parseIPPart(ip, shift) for ip, shift in ips_shifts]    return sum(addr)def parseCIDR(cidr):    addrString, bitsString = cidr.split('/')    try:        bits = int(bitsString)    except TypeError:        bits = 32    addr = parseIP(addrString)    return addr, bitsclass CIDRTree:    class CIDRNode:        def __init__(self, depth):            self.depth = depth            self.isset = None            self.unset = None            self.leaf = False    def __init__(self):        self.root = CIDRTree.CIDRNode(-1)    def addCIDR(self, cidr):        ip, bits = parseCIDR(cidr)        node = self.root        for b in range(bits):            if node.leaf:                # Previous bigger CIDR Covers this subnet                return            mask = 1 << (31 - b)            if (ip & mask) != 0:                if node.isset is None:                    node.isset = CIDRTree.CIDRNode(b)                kid = node.isset            else:                if node.unset is None:                    node.unset = CIDRTree.CIDRNode(b)                kid = node.unset            node = kid        # node is now a representation of the leaf that comes from this CIDR.        # Clear out any more specific CIDRs that are no longer relevant (this CIDR includes a previous CIDR)        node.isset = None        node.unset = None        node.leaf = True        #print(Added CIDR , ip,  and bits , bits)    def matches(self, ipString):        ip = parseIP(ipString)        node = self.root        shift = 0        while node is not None and not node.leaf:            shift += 1            mask = 1 << (32 - shift)            val = (ip & mask) != 0            node = node.isset if val else node.unset        return node is not None and node.leafif __name__ == __main__:    cidrTree = CIDRTree()    cidrTree.addCIDR(8.0.0.0/8)    cidrTree.addCIDR(9.8.7.0/24)    print (Tree matches 8.8.8.8:, cidrTree.matches(8.8.8.8))    print (Tree matches 9.9.9.9:, cidrTree.matches(9.9.9.9))    print (Tree matches 9.8.7.6:, cidrTree.matches(9.8.7.6))