Learn how easy it is to sync an existing GitHub or Google Code repo to a SourceForge project! See Demo

Close

#6 Docs should mention tombstoning

closed-invalid
Cliff Click
None
5
2009-08-11
2009-07-27
Jonathan Ellis
No

Tombstoning is not transparent to the end user because (according to my quick read of the code; I could not find this documented anywhere) keys are not actually cleared by remove() until growing the map pushes things into a new table.

This bit me when I was using a NBHS to store very large data structures, and it was very frustrating to run out of memory while the Set said it was empty!

If the docs had mentioned this property it would have been clear what was going on.

Also, if print() actually called the private print instead of print2 it would again have been obvious. (Since I believed the docstring saying that the public method indeed revealed the "internal" state this sent me off in the wrong direction for a while.)

Discussion

  • Cliff Click
    Cliff Click
    2009-08-11

    Keys & Values are not kept around after a remove; instead a Tombstone is inserted into the table. This will keep only the backing array 'full' until a resize, but it will not consume any other storage than the backing array. In particular, large things put in a Set and then removed will NOT be kept alive by the Set.

    If you have a counter-example, please send it to me.

    Cliff

     
  • Cliff Click
    Cliff Click
    2009-08-11

    • assigned_to: nobody --> cliffclick
    • status: open --> closed-invalid