Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

runtime: node ordering in mTreap #28805

Closed
jerrinsg opened this issue Nov 15, 2018 · 19 comments
Closed

runtime: node ordering in mTreap #28805

jerrinsg opened this issue Nov 15, 2018 · 19 comments
Labels
FrozenDueToAge NeedsFix The path to resolution is known, but the work has not been done.
Milestone

Comments

@jerrinsg
Copy link
Contributor

I had a question about how spans are stored in the mTreap datastructure.

mgclarge.go mentions that the treap is sorted by page size, and for spans of the same size, the secondary sort is done based on span start address. But I see that the insert() function in mgclarge.go compares the address of the span datastructure, rather than using the span base address.

 	else if uintptr(unsafe.Pointer(t.spanKey)) < uintptr(unsafe.Pointer(span)) {
		// t.npagesKey == npages, so sort on span addresses.
		pt = &t.right
	} else if uintptr(unsafe.Pointer(t.spanKey)) > uintptr(unsafe.Pointer(span)) {
		pt = &t.left
	} 

Shouldn't this check be rather

	else if t.spanKey.base() < span.base() {
		// t.npagesKey == npages, so sort on span addresses.
		pt = &t.right
	} else if t.spanKey.base() > span.base() {
		pt = &t.left
	} 
@odeke-em
Copy link
Member

Thank you for the question @jerrinsg!

I'll kindly page some experts @aclements @RLH

@odeke-em odeke-em added the NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one. label Nov 15, 2018
@aclements
Copy link
Member

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

@aclements aclements added this to the Unplanned milestone Nov 15, 2018
@aclements aclements added NeedsFix The path to resolution is known, but the work has not been done. and removed NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one. labels Nov 15, 2018
@jerrinsg
Copy link
Contributor Author

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?

@aclements
Copy link
Member

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.

@Skarlso
Copy link
Contributor

Skarlso commented Nov 22, 2018

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

@aclements
Copy link
Member

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

@Skarlso
Copy link
Contributor

Skarlso commented Nov 24, 2018

On it! Cheers. :)

@Skarlso
Copy link
Contributor

Skarlso commented Nov 24, 2018

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

@Skarlso
Copy link
Contributor

Skarlso commented Nov 24, 2018

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

@Skarlso
Copy link
Contributor

Skarlso commented Nov 24, 2018

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

@jerrinsg
Copy link
Contributor Author

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

@aclements
Copy link
Member

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.

@Skarlso
Copy link
Contributor

Skarlso commented Nov 27, 2018

@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. :)

@Skarlso
Copy link
Contributor

Skarlso commented Nov 27, 2018

@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? :)

@gopherbot
Copy link

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

@mknyszek
Copy link
Contributor

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.

@Skarlso
Copy link
Contributor

Skarlso commented Nov 28, 2018

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

@mknyszek
Copy link
Contributor

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.

@Skarlso
Copy link
Contributor

Skarlso commented Nov 29, 2018

@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.

@golang golang locked and limited conversation to collaborators Nov 29, 2019
Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Labels
FrozenDueToAge NeedsFix The path to resolution is known, but the work has not been done.
Projects
None yet
Development

No branches or pull requests

6 participants