Bitstream decoding is slow

2013-09-09
2013-09-10
  • Andreas Moser
    Andreas Moser
    2013-09-09

    I couldn't figure out how to file a bug / submit a patch on this site so I will just post this here. Sorry for that.

    The BitStringDecoder for ber is super slow since it decodes the stream bit by bit. I improved this by precomputing the bit lists and brought down the runtime for parsing the google.com cert to ~50% (total time, not just bitstream parsing time). I uploaded the patch of what I did here:
    https://docs.google.com/file/d/0B5xwh2wRbmxsVWw0TlhmbmJtWTg/edit?usp=sharing

    Maybe this helps...

     
  • Ilya Etingof
    Ilya Etingof
    2013-09-10

    Thanks for the patch!

    I will see if I could improve BIT STRING handling performance beyond the precomputed values approach and report back here.

    Current BIT STRING performance is just awful. %(

     
  • Andreas Moser
    Andreas Moser
    2013-09-10

    If you don't like the precomputed values approach, the most important problem to address in the current code is the accumulation of bits in a tuple. Tuples are imutable so this is essentially a quadratic algorithm.

    If you just change this to be a list instead, it's already much faster. Not as fast as doing it byte wise with precomputation though :)

     
  • Ilya Etingof
    Ilya Etingof
    2013-09-10

    That's right, I'm looking into a byte wise design with some precomputation.

    Original implementation was more of a proof of concept. %-\