Promote the header byte jump table to a constant

[zslayton]

The create_header_byte_jump_table function in binary/header.rs will parse each possible byte value from 0 to 255 as though it were the one-octet type descriptor found at the beginning of all binary Ion values. The output from parsing each byte is stored in a newly allocated Vec that can be used as a jump table to avoid re-calculating the meaning of same byte values repeatedly.

This is sub-optimal:

• It requires a Vec to be allocated when a fixed-size array would do
• It requires entities that wish to use the jump table to maintain their own copy of the Vec despite the fact that its contents will always be identical.

Ideally, we would store a fixed-length array as a static constant in the header module. Unlike C, however, the Rust compiler tries very hard to prevent programs from mutating global state. This means that initializing a static array is currently somewhat difficult to do without sacrificing either speed or safety.

Here are some options I've explored:

safe + slow

The lazy_static crate provides a macro that allows you to declare and initialize a global constant. It works by wrapping your constant in a custom smartpointer type--the first time the pointer is dereferenced, lazy_static will call a user-defined function to calculate the value of the constant. Every dereference that occurs from then on will receive the already-calculated value.

This is easy to implement, but profiling with valgrind has shown that the indirection introduced by the smartpointer indirection adds an unacceptable amount of overhead in terms of CPU time. Derefencing the jump table each time you begin parsing a value in a stream with millions of values adds up quickly.

thread_local copies of the jump table suffer from even worse indirection overhead, rendering them a non-starter.

If/when we add an IonSystem concept, we may be able to have IonReaders share a reference to a shared jump table living in the IonSystem, but this may not be worth the complexity.

unsafe + fast

Initializing a fixed-size array (i.e. [T], not a Vec) is currently surprisingly challenging for non-trivial types. The best methods available only work for types that implement the Copy trait, and types that implement Default and where the array is <32 entries long.

We could choose to skirt this problem with unsafe code, but this has its own problems:

• The compiler cannot guarantee the memory safety of unsafe code, so we would need to scrutinize it very carefully.
• Because the array would be initialized at runtime (not build time), we would need to design an appropriate synchronization mechanism to guarantee that readers didn't reference the jump table before it was initialized.
• The APIs for working with not-yet-initialized data are in a state of flux. The Rust ecosystem is migrating away from mem::uninitialized (currently deprecated in nightly) and towards mem::MaybeUninit (currently unstable).

safe + fast + not possible yet

Rust is incrementally adding support for const fns, functions whose outputs can be calculated entirely at compile time. This is perfect for our use case -- all of the inputs are statically known (u8 values from 0 to 255) and processing them requires no information from the outside world. With this feature, we'll be able to simply write:

const HEADER_JUMP_TABLE: [IonResult<Option<IonValueHeader>>] = create_jump_table();

The compiler will calculate the definition of HEADER_JUMP_TABLE at build time and then all interested entities can refer to it freely -- no wasted memory, no additional overhead from indirection.

At the time of this writing, const fns have severe restrictions on which language features may be used. Functionality like match statements, the ? operator, calling non-const functions, looping, etc. are planned but not yet supported. These restrictions are so limiting that I have not been able to write an array initialization const fn.

[dlurton]

I'm quite far from being a rust expert so this could be really far off but is there a reason why this wouldn't work in the global scope?

let headers: [IonValueHeader; 255] = [
    IonValueHeader::from_byte(0),
    IonValueHeader::from_byte(1),
    IonValueHeader::from_byte(2),
    ...
    IonValueHeader::from_byte(255),		
];

Warning: I didn't even try to compile this -- modified from the examples here: https://www.joshmcguigan.com/blog/array-initialization-rust/

[zslayton]

In order to use a function call to initialize a static (global) value, that function must be a const fn (described above) so its return value can be computed at compile time. You can't call IonValueHeader::from_byte because it isn't const. I've taken a few cracks at trying to rewrite it to be const, but the current language feature restrictions for const fns are so limiting (matching, looping, and non-const fn calls are all currently not supported) that I haven't had any success.

You can read a nice summary of why initializing statics is complicated here. It's a few years old, but still holds up -- the only major change since then has been the introduction of const fn.

[dlurton]

I took a stab at rewriting those functions to be const fn this weekend. More thought is required than I had time for because using conditionals such as match and if in a const fn is not yet stable. (This is what you were saying as the final option above.) You can enable it now in the current stable build of rustc, but doing so comes with a risk that we might depend on some aspect that changes when RFC 2342 becomes stable.

[zslayton]

You can enable it now in the current stable build of rustc

Oh? Is there a #[feature(...)] flag to enable it? I wasn't able to find one.

but doing so comes with a risk that we might depend on some aspect that changes when RFC 2342 becomes stable.

ion-rust uses trait specialization anyway, so it's already got one unstable feature enabled.

[dlurton]

Looks like some experimental features regarding const fn can be enabled with #![feature(const_fn)] . I tried this but now it gives errors like below, so no, it looks like support is not complete even with the feature flag.

error[E0019]: constant function contains unimplemented expression type
  --> src/binary/type_code.rs:40:13
   |
40 |             NullOrWhitespace => IonType::Null,

[zslayton]

Using match, if, and loop in const contexts has been stabilized and will land in Rust 1.46, due sometime towards the end of August. 🎉

This should unblock not only the header byte jump table, but also some fun optimizations for encoding binary scalars.

[zslayton]

Rust 1.46 landed yesterday. After some experimentation, I've concluded that this is now possible but very painful. Some remaining limitations are easily worked around (Can't use a for loop, but can use while), but others would require extensive rewrites.

Several helper functions would need to be rewritten to avoid producing intermediate values that get dropped.

error[E0493]: destructors cannot be evaluated at compile-time
  --> src/binary/header.rs:75:27
   |
75 |         let entry = match Header::from_byte(byte_value) {
   |                           ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ constant functions cannot evaluate destructors
...
78 |         };
   |          - value is dropped here

These values are simple enums and do not have custom implementations of Drop -- the compiler is just that restrictive for the time being.

We might be able to get around this by inlining the source for these functions (or writing them as macros), but it makes the code a lot less readable and probably isn't worth it at this point. I'll check in again in 6 weeks when Rust 1.47 lands. :)