611484 - Bargain-basement bibop boxes

Status: VERIFIED FIXED

(Tamarin Graveyard :: Virtual Machine, defect)

Description

[Lars T Hansen]

In the *long* term we need to redesign our tagging scheme because we're running out of tags and the tags that we have are not assigned well for common operations (0 should be the int tag, for example).

In the *short* term we need some breathing room to provide support for a number of new primitive (non-pointer-containing) value types: float, float2, float3, float4, float4x4, maybe decimal, maybe some other things.  ("Short term" means the work is starting now.)

Observe that all those value types are fixed-size and relatively small.  If we segregate their allocation by type (Number on this page, float4 on that page, and so on) we can share a single pointer tag (using the one we're currently using for Number will be OK for now) and we can encode the actual type in the first word of the page header.

The advantage of segregated BiBoP allocation is that we can remain headerless, which will matter for many of these types (they're small or they have bizarre alignment requirements, and they have no vtable or reference count field anyway).

This scheme will slow down untyped arithmetic on Numbers and comparison of Numbers a little bit because there's a separate mask and load to get the type tag.  (Basically, if the tag is 7 the tag is replaced by the tag we get when loading the first word from the page head; after that the code is the same.)  And there's always the risk that somebody is making assumptions about tag 7, so we should expect a little turbulence.  But overall it seems like the simplest solution in the short term.

Comment 1

[Lars T Hansen]

Approximately 60 uses of kDoubleType in Tamarin and another 30 in the Flash Player - seems manageable.

Comment 2

[Steven Johnson]

(In reply to comment #1)
> Approximately 60 uses of kDoubleType in Tamarin and another 30 in the Flash
> Player - seems manageable.

Don't forget that "kDoubleType" is also used by genericObjectToAtom in oddball cases, for storing GCObjects (that aren't really doubles) into things that requires Atoms. Fixable, just another hack job to unhack.

Comment 3

[Lars T Hansen]

How could I forget?  :-)  I have this crazy idea that the level of indirection created here might actually be beneficial: it'll be straightforward(?) to create a kind of "foreign-pointer box" that allows doubles to be set apart from genericObjects.  But we'll see.

Comment 4

[Lars T Hansen]

Attachment: Segregated allocation for doubles, with support for bibop tagging

Comment 5

[Lars T Hansen]

Attachment: Convert from kDoubleType to kBibopType + kBibopDoubleType

Builds on Mac and Windows.  Tested on Mac, appears to work OK (no, no performance numbers).  I propagated the kDoubleType hack for generic objects into this new patch, using kBibopType - in principle it's no less safe than it used to be, and it's OK for now.

Bibop types are a single byte stored in the first byte of a block.  (The byte was available after a little shuffling of fields, but the block header should not have grown - not verified.)  Thus picking up the bibop tag is relatively cheap: mask off low bits of atom, load byte through that pointer.

Comment 6

[Lars T Hansen]

Attachment: Convert from kDoubleType to kBibopType + kBibopDoubleType

Comment 7

[Steven Johnson]

Is "bibop" really gonna be the final nomenclature?

Yuck.

Comment 8

[Lars T Hansen]

Nothing final about it, but it is standard nomenclature for a type-segregated allocation style (BIg Bag Of Pages).

Comment 9

[Lars T Hansen]

Virgil has some preliminary performance numbers.  They show some worrisome slowdowns on 32-bit microbenchmarks - likely a type test on a hot path in the VM somewhere that gets in the way - but otherwise nothing remarkable; on 64-bit the overall performance seems to be slightly better, if anything.  More data to come.

Comment 10

[Edwin Smith]

some heresay, in case it helps:

Long ago I remember reading about a cache hazard with many accesses to page-aligned locations.  The canonical worst case is a direct mapped cache that can only hold one value whose lower 12bits (assuming 4K page size) are the same, or an N-way cache, limited to N such values.

I would think if this is a problem, that we already have it, since GC structures are at the beginnings of pages, for small blocks at least.  but, BiBoP could make it worse, if its a problem at all.

Comment 11

[Virgil Palanciuc]

Attachment: Convert from kDoubleType to kBibopType + kBibopDoubleType; rebased to latest tamarin-redux

I rebased it to latest tamarin-redux, it wasn't compiling anymore with the latest version of the repository

Comment 12

[Lars T Hansen]

Comment on attachment 491462 [details] [diff] [review]
Convert from kDoubleType to kBibopType + kBibopDoubleType

Obsoleted by Virgil's update.

Comment 13

[Virgil Palanciuc]

Attachment: Convert from kDoubleType to kBibopType + kBibopDoubleType

Fixed the VMCFG_FASTPATH_FROMATOM path for bibop types (in particular, for double; all others still get converted to a call to AvmCore::number).

Comment 14

[Lars T Hansen]

Comment on attachment 504758 [details] [diff] [review]
Convert from kDoubleType to kBibopType + kBibopDoubleType

Seems OK.  You can probably do better by subtracting the kBibopTag from the pointer in the load instruction (so you get an immediate offset) instead of having a separate AND instruction, but I'm not familiar enough with LIR or the jit to know whether it would figure that out on its own.

Comment 15

[Edwin Smith]

Its easy, use the tagged pointer as the pointer, and use -kBibopTag as the offset, instead of 0.  This will become the expected addressing mode.

Comment 16

[Lars T Hansen]

(In reply to comment #14)

> You can probably do better by subtracting the kBibopTag from the
> pointer in the load instruction (so you get an immediate offset) instead of
> having a separate AND instruction ...

Nevermind, I take that back, that would apply in a different situation than here.

Comment 17

[Virgil Palanciuc]

Attachment: Segregated allocation for doubles, with support for bibop tagging

Rebased on Tamarin-redux 5829 : ca2dff3a0624 (replaces Lars' patch; I can't obsolete it myself, bugzilla won't let me).

Comment 18

[William Maddox]

Sorry to be making these comments at this point, but I was not at all aware of this work until I got an email from Virgil today.

I *really* don't like the overloading of kDoubleType for this purpose.  Like kIntptrType, it's something we want to touch frequently and efficiently in inlined code.  Whether we see a significant loss of execution speed or not from the extra crud in the FROMATOM fastpath, it's bloating up the size of the compiled code.  Also, given the exceptionally good branch prediction hardware on the current desktop x86 processors, I'm not going to believe any claims that the performance impact is insignificant unless this can be shown on ARM and Atom as well.

Did anyone consider overloading kBooleanType?  I haven't looked at the details, but it seems like it would be less harmful to inlining.  There's no compelling reason to inline a check for the boolean type tag.  The potential problem that I can see is that Boolean is implemented as a non-pointer type.  I think we could easily eliminate any dependencies on the currently-defined numeric values the boolean atoms, however.  It would then simply be necessary to pin down the addresses of a canonical true and false value.  I don't know the details of the GC, but there may already be address ranges that are understood to represent permanent, immovable objects.

Comment 19

[Virgil Palanciuc]

If we want to change the flag we are using for BiBop - we should also consider kSpecialType; (i.e., kSpecialType |0 == undefined; kSpecialType | non_null_ptr = Bibop pointer)

I haven't changed Flash Player but in Tamarin itself the impact would be minimal.

Comment 20

[Lars T Hansen]

(In reply to comment #18)
 
> Also, given the exceptionally good branch prediction hardware
> on the current desktop x86 processors, I'm not going to believe any claims
> that the performance impact is insignificant unless this can be shown on 
> ARM and Atom as well.

That's a bit convoluted but I believe you're saying that we need performance measurements on ARM and Atom to vet the change.  We know; it's being worked on.  (Well, ARM is being worked on.  We should include Atom I guess.)  Noting will land without those numbers looking good.

> Did anyone consider overloading kBooleanType?

There's a reason why the title of the bug begins with "Bargain-basement": this is a quick and dirty solution.  So far, and a little to my surprise, the performance impact has not been shown to be significant.  So no, nobody considered anything else.

kBooleanType is not a pointer type, and by taking a non-pointer type and recasting it as a pointer type we are basically doing a redesign of our tagging scheme.  For this particular patch I explicitly wanted to avoid that, I wanted something simple that would work to bootstrap the float/float4 work.  When the patch was written it was not intended to land, necessarily, only to remove a blocker from necessary development work.

A redesign of the tagging scheme should go beyond finding space for another pointer and always seemed to me like a fairly large job.  In contrast, the current patch was written in an afternoon.  We could invest more.  (I'm not sure why we should invest more if the performance measurements look good across the board, though.)

> I don't know the details of the
> GC, but there may already be address ranges that are understood to represent
> permanent, immovable objects.

There aren't, but creating permanent objects is trivial.  (And all objects are immovable.)

Comment 21

[Steven Johnson]

(In reply to comment #20)
> kBooleanType is not a pointer type, and by taking a non-pointer type and
> recasting it as a pointer type we are basically doing a redesign of our tagging
> scheme.  

Correct -- changing this will (unfortunately) result in a cascase of subtle code-assumption-failures in various bits of code (and I'll bet you a dollar that not all of them will be in the VM proper).

Comment 22

[William Maddox]

(In reply to comment #19)
> If we want to change the flag we are using for BiBop - we should also consider
> kSpecialType; (i.e., kSpecialType |0 == undefined; kSpecialType | non_null_ptr
> = Bibop pointer)
> 
> I haven't changed Flash Player but in Tamarin itself the impact would be
> minimal.

This is a very attractive possibility, as it avoids the BIBOP complexities for the existing type, which only has a single value.  It slightly complicates AvmCore::isNullOrUndefined(), but will not impact the inline checks emitted by CodegenLIR::emitCheckNull(), because we already check for 'undefined' separately from 'null' in order to throw the correct exception.

Comment 23

[Virgil Palanciuc]

in fact, isNullOrUndefined would remain completely unchanged. The method body is:
((uintptr_t)atom) <= (uintptr_t)kSpecialType
Given that kSpecialType is 4; "undefined" = 4 | 0, whereas any bibop pointer would be 4+some_pointer, i.e., larger than kSpecialType (larger than 4).

But, to reiterate, I didn't investigate Flash Player - Steven and Lars have a point that we would be changing a "non-pointer-type" into a "maybe-pointer-type", and this can potentially have implications outside the VM.

Also, another disadvantage is that the new bibop values would be slightly slower - 3 checks & a memory load, instead of 2 checks & a memory load (we also need to test that the pointer is non-null - i.e. that the value is not "undefined").

Comment 24

[William Maddox]

(In reply to comment #23)
> in fact, isNullOrUndefined would remain completely unchanged. The method body
> is:
> ((uintptr_t)atom) <= (uintptr_t)kSpecialType
> Given that kSpecialType is 4; "undefined" = 4 | 0, whereas any bibop pointer
> would be 4+some_pointer, i.e., larger than kSpecialType (larger than 4).

Good point.

> But, to reiterate, I didn't investigate Flash Player - Steven and Lars have a
> point that we would be changing a "non-pointer-type" into a
> "maybe-pointer-type", and this can potentially have implications outside the
> VM.

Hmm.  Given that 'undefined' is conceptually a placeholder for 'no value at all', I really don't know whether the GC treats it as a non-pointer type, or a 'null-like' pointer type.  Either is superficially plausible.  I suspect things would be easier for player than for kBooleanType, however, because the bit pattern for 'undefined' does not change, so equality/inequality tests against it would be unaffected.  I'd like to hear Steven and Lars chime in on this, however, because they know player and GC, respectively.

> Also, another disadvantage is that the new bibop values would be slightly
> slower - 3 checks & a memory load, instead of 2 checks & a memory load (we also
> need to test that the pointer is non-null - i.e. that the value is not
> "undefined").

On the face of it, this seems an acceptable tradeoff to keep the core Number type as efficient as possible.  The new numeric types are already a bit second-class due to the special role of Number (double) as the universal numeric type inherited from ECMAscript.

How important, in terms of performance, are scalars of the new types going to be, as opposed to specialized aggregate types consumed, e.g., by graphics primitives? If they are performance critical to the same degree as the existing numerics, to what extent to we expect them to appear in untyped code?  (BTW, are we planning to implement new ABC opcodes for efficient type-specialized operations on floats?)

Comment 25

[Lars T Hansen]

(In reply to comment #24)
> 
> Given that 'undefined' is conceptually a placeholder for 'no value at
> all', I really don't know whether the GC treats it as a non-pointer type,
> or a 'null-like' pointer type.

Non-pointer type.  (Null is also a non-pointer type to the GC.)  This probably doesn't matter much; it's only with exact tracing that the GC has started caring about tags at all.

> I suspect things
> would be easier for player than for kBooleanType, however, because the bit
> pattern for 'undefined' does not change, so equality/inequality tests against
> it would be unaffected.  I'd like to hear Steven and Lars chime in on this,
> however, because they know player and GC, respectively.

I think using kSpecialType is probably fine from the point of view of the GC, speaking in isolation about that problem.

> > Also, another disadvantage is that the new bibop values would be slightly
> > slower - 3 checks & a memory load, instead of 2 checks & a memory load
> > (we also need to test that the pointer is non-null - i.e. that the value
> > is not "undefined").
> 
> On the face of it, this seems an acceptable tradeoff to keep the core Number
> type as efficient as possible.  The new numeric types are already a bit
> second-class due to the special role of Number (double) as the universal
> numeric type inherited from ECMAscript.

They are, but they can't be slow...

> How important, in terms of performance, are scalars of the new types going to
> be, as opposed to specialized aggregate types consumed, e.g., by graphics
> primitives? 

We don't know.  We have to assume that they will not be unimportant.

> If they are performance critical to the same degree as the existing
> numerics, to what extent to we expect them to appear in untyped code?

We don't know, but my guess is "not much", and if they do we probably don't care very much.  float / float4 are for graphics math, and people who want performance will learn to use typed code.

> (BTW, are we planning to implement new ABC opcodes for efficient 
> type-specialized operations on floats?)

We don't know, but right now the answer is "no", apart from "pushfloat" and "coerce_f".

IMO it's worth experimenting with using kSpecialType as the bibop pointer.  It might be better not to do that, because that would leave the (very cute) kSpecialType trick available for some other use, but we can always redesign our tagging scheme properly in the future, so let that consideration not be a blocker.

Comment 26

[Steven Johnson]

I'll bet you a dollar that code in Flash/AIR assumes that kSpecialType is a nonpointer -- and I'll bet another dollar that there's code that uses "4" directly, rather than "kSpecialType". (Not saying that's a stopping point, just that extra care in scouring stuff will be necessary.)

Completion of ANI should make this much less painful, but that's not happening short-term.

Comment 27

[Lars T Hansen]

(In reply to comment #26)
> I'll bet you a dollar that code in Flash/AIR assumes that kSpecialType is a
> nonpointer -- and I'll bet another dollar that there's code that uses "4"
> directly, rather than "kSpecialType". (Not saying that's a stopping point,
> just that extra care in scouring stuff will be necessary.)

Since we're just talking small change anyway, would you like to wager anything on abuses of kDoubleType and the number 7?  After all, we're changing the interpretation of that tag with the alternative fix.  It remains a pointer, but what it points to is not the same thing.  kDoubleType was retired so any uses of that name would no longer compile, but of course "7" (or derived values thereof) could still appear.

(Presumably we'd retire the name kSpecialType so that we'd find all occurences of that name too and could rewrite as necessary.)

Comment 28

[Steven Johnson]

(In reply to comment #27)
> (In reply to comment #26)
> Since we're just talking small change anyway, would you like to wager anything
> on abuses of kDoubleType and the number 7?  

Only if I get to bet that such abuses exist.

Comment 29

[Lars T Hansen]

This landed in an altered form as part of the fix for bug #626402.

Comment 30

[Brent Baker]

Lars/Virgil: Is there anything that needs to be done before I can mark this as "Verified"?

Comment 31

[Lars T Hansen]

This one can be retired.