Maximum alignment?

[jfbastien]

What's the maximum alignment for load/store?

We should probably specify something, e.g. log2(address_space_bytes), and test for it.

[mbodart]

By "test for it", I assume you mean just a range check on the alignment value.

If I'm interpreting AstSemantics.md correctly, the alignment is just a performance hint, not a "trappable" guarantee. Is this a correct interpretation?

[jfbastien]

Correct, check it in the implementation, and have corresponding tests in the spec test suite.

Your interpretation is correct.

This came up before somewhere, and I recall some support for the page size being the maximum. If the minimum is one then this could be encoded in 4 bits. But perhaps 256 is also a reasonable limit, encoded in 3 bits, or even 16 encoded in 2 bits. The v8 encoding only has one bit for the alignment - the natural alignment flag.

[kg]

Don't bother worrying about bitpacking. Every stream compressor will do it for you. :-)

@kg That's not my experience. It helps the compressor to pack and avoid unnecessary redundancy. Even brotli only looks back one or two bytes. We should decide on the limits, the lower limit seems to be one and the upper limit at most the page size. We are only interested in powers of 2, so only encode the power of two. The gives fours bits at most. We might be able to do even better given knowledge of the operations natural alignment - brotli only looks at 6 prior bits and might not even notice the difference between the opcodes to focus the codes.

Sorry, if the lower limit is one, that would be 2^0 so four bits only gets to 2^15 which is half of the wasm page size. Similar error in the other suggestions.

[kg]

@kg That's not my experience. It helps the compressor to pack and avoid unnecessary redundancy. Even brotli only looks back one or two bytes. We should decide on the limits, the lower limit seems to be one and the upper limit at most the page size. We are only interested in powers of 2, so only encode the power of two. The gives fours bits at most. We might be able to do even better given knowledge of the operations natural alignment - brotli only looks at 6 prior bits and might not even notice the difference between the opcodes to focus the codes.

I tested this specific question and talked to one of the designers of Brotli. Once you split streams, the alignment values will be a stream of 1 (or 4) byte values which can be arithmetic coded or otherwise represented very efficiently. If we bitpack the alignment into 3-5 bits with other unrelated data in the other bits, what we're actually doing is destroying some of the potential for the compressor to efficiently encode either chunk of data.

Encoding the alignment as a power of two is a perfectly reasonable idea, but if you cap the alignment at some arbitrary threshold so you can pack bits, you may regret it. Vectors >256bytes in size are an inevitability, as are user-defined structures of size >256bytes.

@kg I really doubt that is correct, but we can settle it in a test. Here's why: most of the alignments will be the natural alignment. In a separate stream they will jump around and there is no context. Whereas in inline there is the context of the operator which could predict the natural alignment most of the time, most of the time it would be just one bit. What we might be able to do is optimize the encoding to be 0 for the natural alignment, then when packed in a separate stream it would compress very well.

[kg]

@kg I really doubt that is correct, but we can settle it in a test.

I tested it. It's in js-astcompressor, and you can also see some general things to this effect in the JSZap paper. If you are confused I would be happy to explain it to you in depth offline.

In a separate stream they will jump around and there is no context. Whereas in inline there is the context of the operator which could predict the natural alignment most of the time, most of the time it would be just one bit.

This does bring up an important detail. If your stream splitting is coarse-grained, like 'here is all the uint8s', you're correct that the values will be harder to predict. That's not the right way to do stream splitting (though it is, in fact, better than nothing). You want to split streams semantically, so your individual streams are things like 'opcodes', 'int8 constant immediates' and 'memory load alignments'.

@kg I think I understand your point, but have not explore it. Here's a test.

• A: split out all the load/store alignments into a separate binary file, one byte for each alignment, e.g. hex dump 04 04 04 04 04 04 ... zlib benchmark. Compressed to max with brotli gives 393 bytes.
• B: split out all the natural alignments as zero and non-natural as-is, one byte for each. Same compression gives 13 bytes.

The context helps. Another option would be to keep the one bit flag, in the v8 encoding, and have a separate stream for the non-natural cases, and in that case since most of the alignments are natural this side stream would be very small.

[mbodart]

Is there any data to show that natural alignment is common?

Yes, data is typically naturally aligned when allocated. But given a pointer parameter, say "int *p",
a C/C++ compiler often cannot guarantee that p is well aligned as it most likely hasn't seen
its allocation. Are we expecting C/C++ compilers to optimistically mark references
with natural alignment, and only specify lesser alignment when that is clear to them?

Given that alignment is only a hint, it's utility is not clear to me.

[sunfishcode]

We do expect C/C++ compilers to optimistically mark references with natural alignment, even when they haven't seen the allocation, and only specify lesser alignments with that is clear to them. Natural alignment is the overwhelming majority.

[kg]

@mbodart

Given that alignment is only a hint, it's utility is not clear to me.

The importance of the alignment hint is largely for the polyfill, but it matters on some native architectures too: If we want to do unaligned reads/writes in asm.js we have to jump through some obscene hoops to make them work. So if we don't know the alignment status of any memory operations, we eat a performance hit on all memory traffic.

The alignment hint allows a compiler to say 'it's okay to break me if I lie about my alignment' in the common case so that you only get bad performance in the spots where it's needed.

I agree with @sunfishcode that natural alignment is probably the overwhelming majority in practice. I do think it's the case that some compilers will not trivially be able to flag loads/stores as aligned without doing a full global analysis, though...

[mbodart]

I think we're in agreement, as long as when you say "it's okay to break me" you really mean "it's okay to lessen my performance, but not crash".

I'm not so concerned about MVP. But when simd comes along, the current alignment definition does not allow an engine to choose movaps instead of movups (on X86), as movaps would fault if unaligned. This may be moot as movups performs well on more recent cpus when the data is aligned.

[sunfishcode]

I believe wasm's current alignment hints do permit implementations to use movaps for SIMD, provided they're capable of catching the hardware trap and fixing things up.