html -> gumbo parse tree -> lxml tree
What makes it efficient even with two tree transformations ?
Is one of the above trees constructed in sequential way and is less-recursive ?
The slightly longer answer is that the vast majority of time in parsing is spent actually parsing - examining each character and adjusting your state machine accordingly. When I was benchmarking the gumbo-python bindings, it was 95%+ parsing, < 5% spent on tree construction. Speed up the parsing part by 100x (which isn't all that unreasonable, when you consider that a field reference in Python involves hashing a string and looking up an object in a dictionary attached to the object), and you'll get an equivalent speedup in total runtime that can pay for a lot of tree reconstructions. The Gumbo parse tree itself will often fit in L2 cache (IIRC I'd benchmarked it at about 90% of documents use < 400K RAM), so it doesn't take much time to traverse.
Doing the Gumbo => lxml translation in C rather than Python gives a similar speedup for tree construction: instead of having to lookup fields in Python as dictionary references, you can do it in C by memory offset.
>> benchmarking the gumbo-python bindings, it was 95%+ parsing, < 5% spent on tree construction
95% on parsing - this speeds up since its done in C instead of python - ok. 5% spent on tree construction. I was little surprised with this - I assumed dictionaries might help although construction (seem expensive) for tree but tree traversal becomes optimal.
But as I write this, I find you have mentioned trees in question are of memory OFFSET types. That may explain why its quick. Else DOM styled trees (which I assumed) in C would be expensive to construct and traverse.
Finally, this begs another question : memory offset trees ? How optimal are they in construction since without having knowledge of depth of a tag and its children-depth - this will be have to be a two time parse with some sort of data structure(tree) to maintain book keeping for a second time parse to construct memory offset tree. Can this be done in single parse ? Could you share some insight into this ?