search

larcenists / larceny

Larceny Scheme implementation
Other
202 stars 32 forks source link

Make gctwa O(n) instead of O(n^2) #811

Closed lars-t-hansen closed 7 years ago

lars-t-hansen commented 7 years ago

This is much faster and I think it's still correct. With 200000 dead symbols on the oblist it runs in 90ms instead of 40s on my MacBook Pro.

It's ugly that it writes the proplists of candidate symbols while it's running; to do better we would use a separate hash table.

WillClinger commented 7 years ago

Thank you, Lars. Later today, when I have more time, I will accept this pull request and then simplify it a bit.

lars-t-hansen commented 7 years ago

Thanks, Will. In retrospect it is unnecessary to make the cookie an object, this hammers on the write barrier constantly. #f would be good enough. I think I was trying to preserve the type invariant of the property list field.

Maybe the code ought to be wrapped in call-without-interrupts too.

On Jul 20, 2017 1:08 PM, "Will Clinger" notifications@github.com wrote:

Thank you, Lars. Later today, when I have more time, I will accept this pull request and then simplify it a bit.

— You are receiving this because you authored the thread. Reply to this email directly, view it on GitHub https://github.com/larcenists/larceny/pull/811#issuecomment-316815662, or mute the thread https://github.com/notifications/unsubscribe-auth/AEmYlsmNNmItu9kroE1GRYhMv40FcmWcks5sP7PFgaJpZM4OeYgm .