Page MenuHomePhabricator

[AST] Squeeze some bits in LinkageComputer
ClosedPublic

Authored by riccibruno on Sep 19 2018, 8:49 AM.

Details

Summary

Since Decls are already aligned explicitly to 8 bytes, stash the
3 bits representing an LVComputationKind into the lower 3 bits
of the NamedDecl * in LinkageComputer.

Diff Detail

Repository
rL LLVM

Event Timeline

riccibruno created this revision.Sep 19 2018, 8:49 AM

Does this still work with 32 bit hosts? Does PointerIntPair have 3 bits in that case? Is the alignof static_assert valid in that case?

lib/AST/Linkage.h
40 ↗(On Diff #166137)

I'm not sure how often this ever gets modified, but it is a touch scary to me that we've already maxed out the size of this struct.

89 ↗(On Diff #166137)

Is this not guaranteed by the static-assert in pointerintpair?

Does this still work with 32 bit hosts? Does PointerIntPair have 3 bits in that case? Is the alignof static_assert valid in that case?

I think it does since Decl is manually over-aligned to 8 bytes. But you are right that the static_assert is probably not needed
here since llvm::PointerIntPair checks that the low bits are available.

I'm not sure how often this ever gets modified, but it is a touch scary to me that we've already maxed out the size of this struct.

I am not sure either... It was just a quick change I spotted and this is borderline not worth doing. If you think that we ought to keep
some space left I will abandon this revision.

Does this still work with 32 bit hosts? Does PointerIntPair have 3 bits in that case? Is the alignof static_assert valid in that case?

I think it does since Decl is manually over-aligned to 8 bytes. But you are right that the static_assert is probably not needed
here since llvm::PointerIntPair checks that the low bits are available.

I'm not sure how often this ever gets modified, but it is a touch scary to me that we've already maxed out the size of this struct.

I am not sure either... It was just a quick change I spotted and this is borderline not worth doing. If you think that we ought to keep
some space left I will abandon this revision.

I did a little digging on this, and it seems to be to keep track of a declarations linkage for caching sake. Unless the committees change linkage at all, I guess I don't see this changing much. I think my concerns are assuaged.

That said, I'm adding @george.burgess.iv (or @gbiv ?) to the review, since he's the original author.

Thanks for this! LGTM after erichkeane's comments are resolved.

I did a little digging on this, and it seems to be to keep track of a declarations linkage for caching sake

Yeah, otherwise, we get exponential behavior on some pathological template-y patterns.

lib/AST/Linkage.h
93 ↗(On Diff #166137)

(FWIW, it looks like PointerIntPairInfo::UpdateInt asserts that Kind.toBits() fits nicely in NumLVComputationKindBits. So if anything gets added, it'll yell and we can just revert to the current way of doing this :) )

riccibruno marked 3 inline comments as done.

Removed the superfluous static_assert.

LinkageComputer isn't actually persisted anywhere, right? And there's maybe one computer active at once? So this compression is theoretically saving one pointer of stack space but forcing a bunch of bit-manipulation every time these fields are accessed.

LinkageComputer isn't actually persisted anywhere, right? And there's maybe one computer active at once? So this compression is theoretically saving one pointer of stack space but forcing a bunch of bit-manipulation every time these fields are accessed.

It is not persisted but this saves one pointer per entry in the map. Another factor is that hashing a pair involves hashing
each component and then combining the result, which is comparatively much more expansive than just hashing a PointerIntPair,
which involves only a shift and a xor. The field storing the LVComputationKind is never directly read but only used to differentiate
various kinds of computations in the map. I went back and instrumented the lookup function LinkageComputer::lookup with rdtsc,
and (with all the usual caveats about microbenchmarks and rdtsc) I get that this cuts the number of ticks spent inside lookup
from about 8e6 to 3.5e6. Now of course taking a step back this represent only milliseconds and is firmly in the category of
"way to small to bother", but now we might as well do it.

rjmccall accepted this revision.Sep 21 2018, 10:59 AM

LinkageComputer isn't actually persisted anywhere, right? And there's maybe one computer active at once? So this compression is theoretically saving one pointer of stack space but forcing a bunch of bit-manipulation every time these fields are accessed.

It is not persisted but this saves one pointer per entry in the map. Another factor is that hashing a pair involves hashing
each component and then combining the result, which is comparatively much more expansive than just hashing a PointerIntPair,
which involves only a shift and a xor. The field storing the LVComputationKind is never directly read but only used to differentiate
various kinds of computations in the map. I went back and instrumented the lookup function LinkageComputer::lookup with rdtsc,
and (with all the usual caveats about microbenchmarks and rdtsc) I get that this cuts the number of ticks spent inside lookup
from about 8e6 to 3.5e6. Now of course taking a step back this represent only milliseconds and is firmly in the category of
"way to small to bother", but now we might as well do it.

Oh, I see, the commit summary is wrong. You're not compressing LinkageComputer, you're compressing a lookup key type. LGTM.

This revision is now accepted and ready to land.Sep 21 2018, 10:59 AM

LGTM too.

Thanks again!

This revision was automatically updated to reflect the committed changes.