4 ms·

This is why system programming still matters. Looks like they're missing the obvious optimisation of putting the record data right after the CacheEntry members

by irdc 1mo ago

This is why system programming still matters. Looks like they're missing the obvious optimisation of putting the record data right after the CacheEntry members instead of allocating memory separately though. But that might just be me as a C-programmer talking and not be all that easy in Rust.

deleted 1mo ago
[deleted]
mkeeter 1mo ago
For the curious, this is technically possible in Rust using a dynamically sized type [1], but in practice is difficult and doesn't really play nice with the rest of the language. The nomicon entry concludes with "Yes, custom DSTs are a largely half-baked feature for now." [2] [1] https://doc.rust-lang.org/reference/dynamically-sized-types.html#r-dynamic-sized.struct-field https://doc.rust-lang.org/reference/dynamically-sized-types.... [2] https://doc.rust-lang.org/nomicon/exotic-sizes.html https://doc.rust-lang.org/nomicon/exotic-sizes.html
cobalt 1mo ago
less ergonomic, but still totally doable
sdcfgy 1mo ago
System programming always matters. Things are cheap until they aren't one day.
- tehlike 1mo ago
  things are cheap until you reach a scale.
  - deleted 1mo ago
    [deleted]
  - 9dev 1mo ago
    Things are cheap until they are someone else’s problem, I say!
listeria 1mo ago
Depends on how the CacheEntry is stored, it's probably stored in a slice of &[CacheEntry] which precludes storing the record data alongside it as the size of each entry must be fixed.
- irdc 1mo ago
  This is where hand-rolled intrusive data structures, as are traditional in C, really shine.
  - jmalicki 1mo ago
    Even in C, if you want differently sized data to be indexable in O(1), you're stuck leaving them as pointers. You definitely could just have a variable-sized area for this, but that level of optimization is pretty seldomly done in C.
f311a 1mo ago
Unfortunately, Rust is not a good choice for this kind of tricks. This is where Zig shines. In Rust, you can’t even use proper arenas, which can help a ton with allocations. Cloudflare started to pick Zig recently, for projects, that have memory constraints.
- afdbcreid 1mo ago
  > In Rust, you can’t even use proper arenas You definitely can and this is done a lot. What you might mean is that you can't use standard library's collections with them (this is getting stabilized soon!) and have to use third-party, but that is a different thing than "can't use arenas". > Rust is not a good choice for this kind of tricks. Rust can do those tricks, but it's true that it is hard than in C or Zig. That said there are often crates to help.
  - f311a 1mo ago
    Stabilized soon, really? They did not stabilize it after 10 years and were thinking about different approach. I thought it’s dead.
    - kibwen 1mo ago
      Yes, really. The design has been decided upon ( https://hackmd.io/nNHdKkp1TTK7jat0I-ABqA https://hackmd.io/nNHdKkp1TTK7jat0I-ABqA ) and the implementation has been updated to match ( https://github.com/rust-lang/rust/pull/157428 https://github.com/rust-lang/rust/pull/157428 ). The stabilization PR is just waiting on final approval by the relevant team members, with no remaining concerns currently listed: https://github.com/rust-lang/rust/pull/156882#issuecomment-5350668934 https://github.com/rust-lang/rust/pull/156882#issuecomment-5...
- chlorion 1mo ago
  I'd like to know why I can't use arenas in rust? Especially considering that I have used them before in rust.
  - 1mo ago
cakoose 1mo ago
> putting the record data right after the CacheEntry members I assumed they couldn't do that because they're using it with some kind of generic HashMap<K, V>. In that situation, can "V" be dynamically sized? A dynamically sized "V" would mean you can't have an array of them, which might preclude some hash map implementations.
- esterna 1mo ago
  > All type parameters have an implicit bound of Sized. The special syntax ?Sized can be used to remove this bound if it’s not appropriate. , which HashMap does not do, i.e. the keys and values have to have a statically known size.
- deleted 1mo ago
  [deleted]
jiggawatts 1mo ago
I wish more programming languages implemented record types as seen in databases, where dynamically sized fields are packed into a contiguous area of memory. The CloudFlare manually implemented a clumsy version of this. Wouldn’t it be nice for the compiler to manage this for you in the same way that your database engine does when it saves a “row”?
- anitil 1mo ago
  > dynamically sized fields are packed into a contiguous area of memory Are you able to explain this? Do you mean an N sized array where each entry is either a value or a pointer to a value where the 'pointed-to' values are after the end of the array? I'm trying to underatnd how you'd do this without having to parse M-1 elements to get the Mth entry if you did a [{size0, value0}, ....., {sizeN, valueN}] arrangement
  - toast0 1mo ago
    I think they mean the cache entry is a collection of dynamically sized fields. It would be nicer to store that as a single contiguous allocation, rather than a bunch of pointers to individually allocated dynamically sized items. At least in this case, it might. In a row oriented database, you get a contiguous spot for the whole row even when there are multiple variable width fields.
  - jiggawatts 1mo ago
    There are various ways of implementing this, someone from a C programming background mentioned on option where the heap-allocated record objects aren't fixed size structs, but instead the allocated space is dynamically sized and the struct is just a prefix. So logically you'd have the equivalent of: struct FooRecord { int fixed_sized_field; char some_other_field; string first; string last; string title; } Physically the compiler would generate something like: struct FooRecord { long __length__; int fixed_sized_field; char some_other_field; char* first; char* last; char* title; } Where 'first', 'last', and 'title' are sequentially stored after the struct in the heap memory. There are variants of the above, of course. Instead of pointers the compiler could use lengths, offsets, or a pointer to the end of the variable length field -- this works because the beginning of the first field is at a fixed offset, and then pairs of pointers delimit the rest. You can rely on the heap allocator to track the "__length__" instead, or you can encode it into the record explicitly to make "dynamic sized copies" simple. Windows APIs generally work this way! You create a buffer, put a length in the first field, and then the API call writes a fixed-sized prefix followed by the dynamic-sized fields into the buffer. The 'length' is replaced too, so you know how many bytes to copy out without having to understand the structure. Database engines go one step further and pack multiple "records" into a single "row". They typically store the fields "packed" at the start of the row with 16-bit length or offset markers at the end for the various dynamic sizes. Something like: fixed_sized_field // Row #0 some_other_field first last title fixed_sized_field // Row #1 some_other_field first last title ... empty space ... next_offset // always populated row#1_title_offset row#1_last_offset row#1_first_offset row#1_offset row#0_title_offset row#0_last_offset row#0_first_offset row#0_offset // typically the constant zero The idea here is that every length is the difference between pairs of sequential offsets. I.e. row#1_title has length (next_offset-row#1_title_offset).

by irdc 1mo ago

deleted 1mo ago

[deleted]

mkeeter 1mo ago

For the curious, this is technically possible in Rust using a dynamically sized type [1], but in practice is difficult and doesn't really play nice with the rest of the language. The nomicon entry concludes with "Yes, custom DSTs are a largely half-baked feature for now." [2] [1] https://doc.rust-lang.org/reference/dynamically-sized-types.html#r-dynamic-sized.struct-field https://doc.rust-lang.org/reference/dynamically-sized-types.... [2] https://doc.rust-lang.org/nomicon/exotic-sizes.html https://doc.rust-lang.org/nomicon/exotic-sizes.html

cobalt 1mo ago

less ergonomic, but still totally doable

sdcfgy 1mo ago

System programming always matters. Things are cheap until they aren't one day.

tehlike 1mo ago
things are cheap until you reach a scale.
- deleted 1mo ago
  [deleted]
- 9dev 1mo ago
  Things are cheap until they are someone else’s problem, I say!

listeria 1mo ago

Depends on how the CacheEntry is stored, it's probably stored in a slice of &[CacheEntry] which precludes storing the record data alongside it as the size of each entry must be fixed.

irdc 1mo ago
This is where hand-rolled intrusive data structures, as are traditional in C, really shine.
- jmalicki 1mo ago
  Even in C, if you want differently sized data to be indexable in O(1), you're stuck leaving them as pointers. You definitely could just have a variable-sized area for this, but that level of optimization is pretty seldomly done in C.

f311a 1mo ago

Unfortunately, Rust is not a good choice for this kind of tricks. This is where Zig shines. In Rust, you can’t even use proper arenas, which can help a ton with allocations. Cloudflare started to pick Zig recently, for projects, that have memory constraints.

afdbcreid 1mo ago
> In Rust, you can’t even use proper arenas You definitely can and this is done a lot. What you might mean is that you can't use standard library's collections with them (this is getting stabilized soon!) and have to use third-party, but that is a different thing than "can't use arenas". > Rust is not a good choice for this kind of tricks. Rust can do those tricks, but it's true that it is hard than in C or Zig. That said there are often crates to help.
- f311a 1mo ago
  Stabilized soon, really? They did not stabilize it after 10 years and were thinking about different approach. I thought it’s dead.
  - kibwen 1mo ago
    Yes, really. The design has been decided upon ( https://hackmd.io/nNHdKkp1TTK7jat0I-ABqA https://hackmd.io/nNHdKkp1TTK7jat0I-ABqA ) and the implementation has been updated to match ( https://github.com/rust-lang/rust/pull/157428 https://github.com/rust-lang/rust/pull/157428 ). The stabilization PR is just waiting on final approval by the relevant team members, with no remaining concerns currently listed: https://github.com/rust-lang/rust/pull/156882#issuecomment-5350668934 https://github.com/rust-lang/rust/pull/156882#issuecomment-5...
chlorion 1mo ago
I'd like to know why I can't use arenas in rust? Especially considering that I have used them before in rust.
- 1mo ago

cakoose 1mo ago

> putting the record data right after the CacheEntry members I assumed they couldn't do that because they're using it with some kind of generic HashMap<K, V>. In that situation, can "V" be dynamically sized? A dynamically sized "V" would mean you can't have an array of them, which might preclude some hash map implementations.

esterna 1mo ago
> All type parameters have an implicit bound of Sized. The special syntax ?Sized can be used to remove this bound if it’s not appropriate. , which HashMap does not do, i.e. the keys and values have to have a statically known size.
deleted 1mo ago
[deleted]

jiggawatts 1mo ago

I wish more programming languages implemented record types as seen in databases, where dynamically sized fields are packed into a contiguous area of memory. The CloudFlare manually implemented a clumsy version of this. Wouldn’t it be nice for the compiler to manage this for you in the same way that your database engine does when it saves a “row”?

anitil 1mo ago
> dynamically sized fields are packed into a contiguous area of memory Are you able to explain this? Do you mean an N sized array where each entry is either a value or a pointer to a value where the 'pointed-to' values are after the end of the array? I'm trying to underatnd how you'd do this without having to parse M-1 elements to get the Mth entry if you did a [{size0, value0}, ....., {sizeN, valueN}] arrangement
- toast0 1mo ago
  I think they mean the cache entry is a collection of dynamically sized fields. It would be nicer to store that as a single contiguous allocation, rather than a bunch of pointers to individually allocated dynamically sized items. At least in this case, it might. In a row oriented database, you get a contiguous spot for the whole row even when there are multiple variable width fields.
- jiggawatts 1mo ago
  There are various ways of implementing this, someone from a C programming background mentioned on option where the heap-allocated record objects aren't fixed size structs, but instead the allocated space is dynamically sized and the struct is just a prefix. So logically you'd have the equivalent of: struct FooRecord { int fixed_sized_field; char some_other_field; string first; string last; string title; } Physically the compiler would generate something like: struct FooRecord { long __length__; int fixed_sized_field; char some_other_field; char* first; char* last; char* title; } Where 'first', 'last', and 'title' are sequentially stored after the struct in the heap memory. There are variants of the above, of course. Instead of pointers the compiler could use lengths, offsets, or a pointer to the end of the variable length field -- this works because the beginning of the first field is at a fixed offset, and then pairs of pointers delimit the rest. You can rely on the heap allocator to track the "__length__" instead, or you can encode it into the record explicitly to make "dynamic sized copies" simple. Windows APIs generally work this way! You create a buffer, put a length in the first field, and then the API call writes a fixed-sized prefix followed by the dynamic-sized fields into the buffer. The 'length' is replaced too, so you know how many bytes to copy out without having to understand the structure. Database engines go one step further and pack multiple "records" into a single "row". They typically store the fields "packed" at the start of the row with 16-bit length or offset markers at the end for the various dynamic sizes. Something like: fixed_sized_field // Row #0 some_other_field first last title fixed_sized_field // Row #1 some_other_field first last title ... empty space ... next_offset // always populated row#1_title_offset row#1_last_offset row#1_first_offset row#1_offset row#0_title_offset row#0_last_offset row#0_first_offset row#0_offset // typically the constant zero The idea here is that every length is the difference between pairs of sequential offsets. I.e. row#1_title has length (next_offset-row#1_title_offset).