#Creating a compile-safe Log2Lookup table.

1 messages · Page 1 of 1 (latest)

valid oriole
#

I would like to specify (somehow), that there is a table
that accepts numbers from some power of 2 up to another power of 2,
e.g. 8 -> 8192 which is 3 -> 13 in log2.

Is it possible to specify the Log2Lookup table such that I can put a type
on get() which will only accept values from 8 -> 8192, otherwise a compile error?

The job of the table is essentially to round memory allocation amounts up to the next
power of 2 and return some object from a table accordingly.

```rust
const std = @import("std");

// The export was just for looking in godbolt, not relevant.
export fn foo(x: usize) usize {
    const table = Log2Lookup(u64, 3, 13){
        .lookup = .{ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 },
    };
    return table.get(x);
}

fn Log2Lookup(
    comptime T: type,
    comptime log2lower: u8,
    comptime log2upper: u8,
) type {
    const n_entries = log2upper - log2lower + 1;

    return struct {
        const Self = @This();

        lookup: [n_entries]T,

        fn get(self: *const Self, size: usize) T {
            // Would need to runtime check here that size is suitable, (log2_int_ceil(size) <= log2upper)
            const idx = std.math.log2_int_ceil(usize, size) - log2lower;
            return self.lookup[idx];
        }
    };
}
```
tiny island
#

zig may get ranged ints in future, for now status quo is:
const Index = std.math.IntFittingRange(8, 8192);
and doing assert in the get function for the range as well.

#

the IntFittingRange only returns uXX that fits the range, but won't actually bound check

#

though if your lookups are with comptime known constants, then make size: -> comptime size: and it can be checked compile time.

valid oriole
#

Thank you! Didn't know about the IntFittingRange, will take a closer look. Played around with Log2Int but wasn't getting anywhere compile time checking useful.

But thanks for the heads up that there's no defacto answer at this point, will stick with the assert, I'd love to comptime it but can't

tiny island
#

Well if your get function size parameter is always compile time known, then you can for sure check the range compile time

#

otherwise, even with ranged ints the check ultimately will be runtime

valid oriole
#

I meant more that the type with size: usize could be size: blah and lift the responsibility of runtime checking to the caller to ensure they have a blah type

#

As it stands, I could use this blah type in quite a few places to replace passing around usizes which need to obey certain properties doesn't make it very clear without adding a bunch of documentation around the place

#

Sorry to be a little clearer, I mean the caller would have to do a runtime check to convert a usize into a blah to pass it to get()

tiny island
# 
pub const Blah = enum (std.math.IntFittingRange(8, 8192)) {
  _,

  pub fn init(num: usize) @This() {
    std.debug.assert(num >= 8 and num <= 8192);
    return @enumFromInt(num - 8);
  }

  pub fn index(self: @This()) usize {
    return @intFromEnum(self) + 8;
  }
}
#

^ this would be basically typed int and it would only be runtime checked during init

valid oriole
#

Damn, nice use of an enum, will give it a go, many thanks!

tiny island
#

packed struct can be used as well for similar effect

#

but typically people use enum for this

valid oriole
#

I'll stick this into godbolt and see if there's any overhead with this but looks like most of it could get compiled away

tiny island
#

the only overhead would come from the assert pretty much, if you want to micro-optimize, you can make the backing int u16 and remove the - 8 and + 8

#

the enumFromInt prob needs @intCast as well

#

but the init could just take u16 as well (and index return u16 as well)

valid oriole
#

I'll play around but this should be good enough to get me started for sure. I don't think the u16 except for denser packing if needs be but that's gonna take some real benchmarking and not a "less instructions, more juice"