search

sestoft / C5

C5 generic collection library for C#/.NET
http://www.itu.dk/research/c5/
MIT License
1.03k stars 181 forks source link

HashedLinkedList raises assertion error when adding lots of elements #17

Closed ovidiomanteiga closed 2 months ago

ovidiomanteiga commented 10 years ago

C5 HashedLinkedList raises an assertion error at the method splittaggroup when adding lots of elements. In the attached image example, the list had close to 4 million integers.

As the debugger shows, previous-taggroup-tag (ptgt) is equal to int.MaxValue - 1 and next-taggroup-tag (ntgt) is equal to int.MaxValue. So those values do not verify the assertion that ptgt + 1 <= ntgt - 1.

"The C5 Generic Collection Library for C# and CLI" technical report states at section 13.8 Implementation of hashed linked lists:

Note, however, that the typical case of always inserting at the end of the list seems to be close to the worst-case scenario for maintaining the tags.

That is the case.

You can run this simple program that tries to reproduce this error: https://github.com/ovidiomanteiga/C5HashedLinkedListAssertionError

c5hashedlinkedlistassertionerror

ondfisk commented 10 years ago

HI Ovidio, I have just tried to run your program on the latest release of C5 (from NuGet). I cannot reproduce the error. Which version are you using?

ovidiomanteiga commented 10 years ago

Hi Rasmus,

I used a version I compiled from a clone of the source code and I retargeted to the .NET Framework 4, instead of the Portable Class Library. I did that in order to use it in an NPerf Fixture https://github.com/ovidiomanteiga/NPerf.Fixtures/tree/master/src/NPerf.Fixture.IList. The version was "Release 2.2.4822.42600 of 2013-03-15" (from the RELEASE-NOTES.txt file).

I have pushed a zip file with the binaries I used, including C5.dll, to my repo at https://github.com/ovidiomanteiga/C5HashedLinkedListAssertionError/blob/master/C5HashedLinkedListAssertionError/bin.zip.

Finally, here you can find a brief list of the features of the machine where I ran the test... https://github.com/ovidiomanteiga/NPerf.Fixtures/blob/master/docs/ISerializerDocs.md#the-execution-environment

ondfisk commented 10 years ago

Hello again. I've just published a new version which includes a .NET 4.0 build, which does not require you to rebuild. The issue, however, is not fixed.

ondfisk commented 2 months ago

Issue fixed in version 3.0