Thank you for the question @jerrinsg!

I'll kindly page some experts @aclements @RLH

Thanks @jerrinsg. You're completely right that the comment and the code disagree. Probably the code should do what the comment says. I don't think it ultimately matters, except that the code is pretty surprising. :)

/cc @mknyszek

Doesn't using span base address to order the nodes in the treap promote spans representing a lower address space range get reused over others? Can the same be said if the pointer to the span datastructure is used for sorting?

Yes, if we ordered spans by base address, the allocator would prefer lower-addressed spans (though it would first prefer better fit spans). The same is certainly not true of the current ordering. But it's not clear that it actually matters. Spans would coalesce differently, but I don't think they would coalesce in a better or worse way.

I kindly ask if I can take over this issue and provide a possible fix? Or is someone working on this already? :) Cheers.

@Skarlso, go for it. :) Send the CL to austin and mknyszek.

On it! Cheers. :)

@jerrinsg I wonder. This seems to me if you are correct, that means that removeSpan does the same incorrect compare.

Also, it appears that this file and the mTreap struct has no tests what os ever. :((( Sad.

Before I even begin to dismantle this, I need to have some strong suit of tests.

@Skarlso Yes, if you change insert() then it looks like you should change removeSpan as well.

Also, it appears that this file and the mTreap struct has no tests what os ever. :((( Sad.

Tests would be nice, but also basically all memory allocation will break if the mTreap is wrong, so this is not poorly-tested code.

@aclements Thanks for the heads up on that! Reading this I was fairly certain that it would possibly be tested elsewhere. I'll try to add some tests though just to adhere to scout rules. Leave things better than found. :)

@jerrinsg Cheers, awesome. :)

@jerrinsg @aclements Please correct me if I'm incorrect here, but I was wondering if this is essentially the same?

uintptr(unsafe.Pointer(t.spanKey)) vs t.base() which is the starting address derived from t.spanKey.base().

I'm not saying that don't change it, because this way it will be more readable, I was just wondering, if it's essentially doing the same thing now and that's why it's not causing any serious problems.

I'm not a 100% sure but unsafe.Pointer would give back the beginning memory address of t.spanKey and convert that to uintptr. Arriving at the same integer which would be the startAddr.

Or I'm mistaken? :)

Change https://golang.org/cl/151499 mentions this issue: runtime: node ordering in mTreap; adjust code to reflect description.

If you insert a println to print out t.spanKey.base() and uintptr(unsafe.Pointer(t.spanKey)) you'll notice that they're different. :)

t.spanKey refers to an mspan structure, but that mspan structure owns some region of memory which starts at mspan.base() (or mspan.startAddr) and extends out by mspan.npages 8KiB-sized pages.

Ah yes! I see. Did this happened to have work incidentally then?

Looking over mTreap more closely, as it turns out, the second ordering (previously mspan struct address, now mspan base) doesn't matter at all, it just has to exist.

When we call mTreap.remove() on allocation, it doesn't even use the secondary ordering, it just takes the first best-fit span it finds. The secondary ordering just has to exist for mTreap.removeSpan() and must be unique to the mspan itself (so either its address or its base address work just fine) so we can efficiently find a specific span in the mTreap.

Thank you for your change though, it does align the comments in that file with the code.

@mknyszek Ah, that makes sense! I started playing with it and couldn't make much difference. Almost came to the same conclusion. :) Thank you very much, I hope to contribute more to Go in the future, and hopefully solve some interesting problems and learn some more about the language I love! :)

Also, for the record... I did run all.bash:

ALL TESTS PASSED
---
Installed Go for darwin/amd64 in /Users/hannibal/go
Installed commands in /Users/hannibal/go/bin

Cheers,
Gergely.