Existing type to dump all my strings into?

Help
, ,
1

I writing a small tool that’s going to be processing hundreds of thousand of structs (items). Each one of these items has a string identifier associated with it. Of course, the strings are variable length and completely irrelevant for most of the processing that I’m going to be doing, so I’m thinking:

  1. It’s a string so let’s just store the slice to it in the item. That gives nice constant size items allowing me to have a big array of them. The actual strings can be on the heap, or in an arena.
  2. I could improve on that by changing the slice to an index. That index would lookup in an array of slices. Doing that shrinks my item a little, and helps serialization by getting rid of the pointer.
  3. Rather than just having the strings on the heap, they could be in a large grow-able contiguous buffer. That would remove the pointer completely and have everything index based / easily serializable. Could also add some capacity heuristics to avoid an allocation call for every string.

So something like:

const Item = struct {
    identifier_idx: usize, 
    ...
};

const OffsetSlice = struct {
    offset: usize,
    len: usize
};

var string_lut: ArrayList(OffsetSlice);
var string_buf: GrowableBuffer(u8);

fn get(idx: usize) []const u8 {
    const slice = string_lutt.items[idx];
    return string_buf.base[slice.offset..][..slice.len];

fn append(gpa: Allocator, item: []const u8) Allocator.Error!usize {
    const slice = try string_buf.append(gpa, item);
    try string_lut.append(gpa, slice);
    return string_lut.len; // New index
}

I’m starting to think GrowableBuffer is just an ArrayList of u8, right? Maybe with some capacity heuristics around it to avoid lots of reallocation. …or would I just be abusing it?

This feels like it should be a fairly common pattern. StringArray or ObjectArray … whenever you want an index-able list of variable sized objects. Does anything like this already exist with a name I haven’t thought of?

1 Like
2

Yes.

That’s not abusing it. If you don’t have a way of knowing the capacity, estimating it is the best you can do.

3 Likes
3

My writing style made my meaning ambiguous. I agree the estimation makes things better.

I was referring to using ArrayList(u8) as an unbounded dynamic size buffer and dropping in objects of other types into it. Is that abuse? Feels a bit hacky to me.

4

At that point it becomes more like an Allocator (need to do alignment, etc), and instead you could use an existing arena allocator. However, then you need to store the pointer rather than an index in the referring struct.

5

What you’re proposing with the growable buffer, which as you’ve correctly said is basically just an ArrayList(u8), is generally known as a string table. It’s used in a bunch of things like even the executable you run(assuming Linux).

It’s then also quite easy to deduplicate the strings which is nice if some values are very common. Basically just like a hashmap to an index.

2 Likes
6

Although getting rid of pointers does help if you want to serialize the data, you still might want to consider a data structure that pins the memory (guarantee it doesn’t get reallocated), as it’s a really nice property when interacting with code that expects strings - you don’t have to worry about a realloc (e.g. from growing an arraylist) invalidating a pointer.

There used to be a Segmented List in the standard library (it’s here now). It’s nice because it’s still (reasonably) easy to serialize while guaranteeing any pointer to data it owns will never be invalidated by adding more strings to it.

2 Likes
7

When I want to use such a data structure I just copy it from the zig source code where it is called StringTable: https://codeberg.org/ziglang/zig/src/branch/master/src/link/StringTable.zig

There have been a bunch of posts about this data structure in the past, because it is quite neat in the way it combines the backing array with a hash set that indexes into that backing array (automatically adding de-duplication).

The only thing that needs to be mentioned is that it uses zero terminated strings, so you can’t use it to store strings that contain zeroes, for that you would have to store the length explicitly like with your OffsetSlice (but personally I would use u32 for the strings unless they really can be huge strings).

In my code I also added a fromOwnedSlice method that way I can easily store the backing array in a file and read it in again restoring my string table from the backing array.

pub fn fromOwnedSlice(gpa: Allocator, slice: []u8) !@This() {
    var instance: @This() = .empty;
    instance.buffer = .fromOwnedSlice(slice);
    // rebuild hash table
    var offset: u32 = 0;
    while (offset < instance.buffer.items.len) {
        try instance.table.putContext(gpa, offset, {}, StringIndexContext{
            .bytes = &instance.buffer,
        });

        offset = while (offset < instance.buffer.items.len) : (offset += 1) {
            if (instance.buffer.items[offset] == 0) break offset + 1;
        } else offset;
    }
    return instance;
}
3 Likes
8

Yes and ArrayList already allocates by reserving a growing capacity to avoid too many reallocations, only if you have measured that those in-frequent reallocations are still a problem, I would consider something like a segmented list.

1 Like
9

If the max size and max count of the strings is known, you could use a packed struct instead to encode the length and offset in a u32:

const TableSlice= packed struct (u32) {
    len: u11, // could be smaller
    offset: u21, // these are just off the top of my head
};

I was interning file names for an LSP thing so I just counted the length of the longest file path in my home directory, and the number of all code files on my computer, doubled both, and used that to determine what a reasonable size for each field was.

3 Likes
10

you could also store the length in the string table itself as a sort of header before each string as a variable-length encoded u32. This way for most short strings <= 127 bytes it’s as small as a null terminator, and in the worst case of huge strings 5 bytes, if the string is longer than 2^28-1 bytes. This way the table slice/offset type can be a u32-backed enum without having to juggle max string length vs max capacity tradeoffs.

4 Likes