Use of BitSet in the C# lexer

vsajip

The use of BitSets with no upper bound in the C# lexer could make the Python implementation slow:

private BitSet parsingOnStack = new BitSet(), seenElseStack = new BitSet(), alreadyHandledStack = new BitSet();

That's because the Python implementation would have to potentially reallocate and copy the underlying array each time the bound was extended. Can we fix the size of these sets? I haven't looked at the grammar in detail so I'm not sure what depth makes sense.

revusky

Hi Vinay,

Sorry to be slow to answer this. I didn't realize that there were new messages on this forum. I guess I assumed that I would get email notification of any new messages but I never did.

Anyway, in this case with the BitSets here, I would imagine that they very very rarely need to be resized. These BitSets are used to keep track of certain things, nesting, for the C# preprocessor. (I ended up having to reimplement it, as I guess I told you in an email.) But, I mean, preprocessor directives are rarely nested more than a few levels in a source file. So a BitSet of initial size 16, say, would almost never need to be resized. As a practical question, I guess the standard implementation of BitSet is to hold them in an array of longs (in Java anyway) so the smallest possible initial bitset capacity would be an array with one long, which can already store 64 bits!

So, I guess the answer is that you could perfectly well just start the BitSets with an initial capacity of 64 as in new BitSet(64) and there would basically never be resized. Or actually, to be more precise, new BitSet(64) does the same thing as new BitSet(32) or any arg that is 64 or less, since the initial long buffer is size 1.