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

Comments

Projects
None yet
6 participants
@jerrinsg
Copy link
Contributor

commented Nov 15, 2018

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

This comment has been minimized.

Copy link
Member

commented Nov 15, 2018

Thank you for the question @jerrinsg!

I'll kindly page some experts @aclements @RLH

@aclements

This comment has been minimized.

Copy link
Member

commented Nov 15, 2018

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

@jerrinsg

This comment has been minimized.

Copy link
Contributor Author

commented Nov 15, 2018

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

This comment has been minimized.

Copy link
Member

commented Nov 15, 2018

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

This comment has been minimized.

Copy link
Contributor

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

This comment has been minimized.

Copy link
Member

commented Nov 23, 2018

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

@Skarlso

This comment has been minimized.

Copy link
Contributor

commented Nov 24, 2018

On it! Cheers. :)

@Skarlso

This comment has been minimized.

Copy link
Contributor

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

This comment has been minimized.

Copy link
Contributor

commented Nov 24, 2018

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

@Skarlso

This comment has been minimized.

Copy link
Contributor

commented Nov 24, 2018

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

@jerrinsg

This comment has been minimized.

Copy link
Contributor Author

commented Nov 27, 2018

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

@aclements

This comment has been minimized.

Copy link
Member

commented Nov 27, 2018

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

This comment has been minimized.

Copy link
Contributor

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

This comment has been minimized.

Copy link
Contributor

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

This comment has been minimized.

Copy link

commented Nov 27, 2018

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

@mknyszek

This comment has been minimized.

Copy link
Contributor

commented Nov 27, 2018

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

This comment has been minimized.

Copy link
Contributor

commented Nov 28, 2018

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

@gopherbot gopherbot closed this in 689fae2 Nov 29, 2018

@mknyszek

This comment has been minimized.

Copy link
Contributor

commented Nov 29, 2018

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

This comment has been minimized.

Copy link
Contributor

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.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.