2011-03-10

Python parsing

Ich baue grade einen pure Python parser für OpenPGP Messages nach RFC 4880. Dabei ist mir wieder mal was aufgefallen.

Wenn man einen Parser baut, der eine grosse Datenstruktur analysiert und in Pakete zerlegt, hat man in den meisten Sprachen folgendes Muster:


In C würde man es wohl so machen:

void parse_message(char * input) {
    int len = find_packet_len(input);
    handle_packet(make_packet(input, len)); 
    input += len;
}

In Python ist der naive Ansatz:

def parse_message(input):
  while input:
     packet_len = find_length_of_packet(input)
     packet = input[:packet_len]
     handle_packet(input[:packet_len])
     input = input[packet_len:]

In funktionalen Sprachen entsprechend.

Das Problem ist nun, das Python an dieser  Stelle jeweils eine Kopie des Paketes und eine Kopie des restlichen Inputs anlegt. Letzteres ist leider eine O(n^2) Operation ....

Entweder baut man das parsing also um, indem man input als Array behandelt nur nur über Indizes adressiert:

def parse_message(input):
  start = 0
  while len(input) > start:
    pl = find_length_of_packet(input, start)
    handle_packet(input[start:start + pl])
    start += pl

Oder, man verfolgt weiter den Stil aus dem oberen Beispiel, legt aber einen Wrapper um den input, der das Kopieren verhindert:


class ROList(list):
    def __init__(self, l, start = 0):
        self.__l = tuple(l)
        self.__start = start
        self.__end = sys.maxint


    def __getitem__(self, i):
        return self.__l[self.__start + i]


    def __getslice__(self, start, end):
        #print self, start, end, sys.maxint - end
        res =  self.__class__("")
        res.__l = self.__l
        res.__start = self.__start + start
        if end < sys.maxint:
            res.__end = self.__start + end
        return res


    def __len__(self):
        if self.__end == sys.maxint:
            return len(self.__l) - self.__start
        else:
            return self.__end - self.__start


    def __repr__(self):
        return "%s : %d" % (self.__l, self.__start)

def test_performance(list_type):
    l = list_type(range(1024*1024))
    while l:
        l = l[512:]

if __name__ == "__main__":
    for t in list, ROList:
        start_time = time.time()
        test_performance(t)
        print 'test of %s performance: %f seconds' % (t, time.time() - start_time)