8 ms·
Why Polars rewrote its Arrow string data type
- padthai 2y agoI am getting Vietnam flashbacks of all the small incompatibilities between Numpy arrays and Pandas Series
- grahamjameson 2y agohttps://youtu.be/J0zjJKBK9ys https://youtu.be/J0zjJKBK9ys
- deleted 2y ago[deleted]
- justinsaccount 2y agoIs there a standalone c/c++ implementation of this string type anywhere?
- lor_louis 2y agoIt looks a lot like cedarDB's "german strings". <https://cedardb.com/blog/german_strings/ https://cedardb.com/blog/german_strings/> You could probably write a C++ implementation based on the article. Note that it's not all that useful if you don't plan on searching for text based on their prefix. From my understanding, this is mostly a better way to store SStables in RAM/partially on disk if you mmap.
- o11c 2y agoHm, both the main article and your link are wasteful for strings of length 13-15, which are still pretty common. As a rule for SSO, if you're already take up the bytes unconditionally, it's going to be worth complexifying your "size" calculation to squeeze a little more into the no-alloc case. That said, note that there are a lot of strings around 20 bytes (stringified 64-bit integers or floats), so pushing to 24-1 is a reasonable choice too. I'd use 3 size classes: * 0-15 bytes, stored in-line. If you need C-string compatibility (which is fairly likely somewhere in your application), ensure that size 15 is encoded as a zero at the last byte. * up to 3.75GB (if my mental math is right), stored with a mangled 32-bit size. Alternatively you could use a simpler cutoff if it makes the mangling easier. Another possibility would be to have a 16-bit size class. * add support for very large strings (likely with a completely different allocation method) too; a 4GB limit sucks and is easily exceeded. If need be this can use an extra indirection. Honestly, with a 16-byte budget, I'd consider spending more of that on the prefix - you can get 8 bytes with enough contortion elsewhere. Duplicating the prefix is probably worth it in more cases than you might think, since it does speed up comparisons. Just remember, you have to check the size to distinguish "a\0" from "a" too, not just from "a\0\0\0\0".
- lor_louis 2y agoYeah I tend to work with strings data around the 15 to 30 ish char count so I'm also sceptical of german strings when it comes to raw memory usage. What really interests me, is that in theory, an SSTable built from German Strings that point into a larger text buffer further down could result in less pagefaults during a binary search? Maybe?
- o11c 2y agoI mean, if you're doing binary searches, the first thing to do is to switch to Eytzinger searches (at least for the prefixes; it's unclear if Eytzing-sorting large strings matters) which are much more cache friendly. (incidentally, Eytzinger was Austrian, not German - same language though!) Second, I'd probably switch to struct-of-array instead of array-of-struct, since the search part only needs the (head of the) key. Possibly some trie-like logic would also help (that is, avoid duplicating the common prefix, instead point to an array of continuations rather than a single one), but beware of costly indirections. Third, I would make sure the user is able to specify the SSO limit, since different domains will have different requirements. Fourth ... if you're column-oriented (or for simple data in the first place), consider implicit union of different `Set` (or whatever) implementations. For example, store all short strings in one array, and all long strings in a different array.
- lor_louis 2y agoI did not know about Eytzing-sorting, I'll look into it after my vacation, thanks! And yeah our current system is column oriented, and I already tried most of your recommendations (including tries) but the biggest limitation we face is that different kinds of queries will be better served by different kinds of data structures but you can only store a few of them on disk before the cost to index becomes too big.
- o11c 2y agoWhoops, I dropped the "er" the second time. I've also seen it labeled "cache-friendly binary sort", and sometimes the Breadth-First-Search aspect is played up (but that's unsearchable). Logical-order (in-order DFS) iteration is obvious and trivial (though a lot of tasks are fine with physical-order (BFS) iteration. Beware that some tasks that nominally don't care about input order perform much better on already-sorted input though). Conversion between logical index and physical index (if you need it - chances are you don't) can still be done efficiently, but requires some (fun!) thought especially for the non-power-of-2 tail. Explicit prefetching is trivial to arrange for k-great grandchildren if needed (though the width of course grows exponentially). Using an n-ary rather than binary tree is possible but I'm not sure of the cache effects in practice. Switching to linear search just at the last level may be worth it? All of this means more complex logic though.
- twic 2y agoAs an aside, what is "German" about these?
- danvonk 2y agoThey were developed by the database group at TU Munich.
- ismailmaj 2y agoI might have missed it in the article but I'm not sure why the prefix is stored for strings that can't be inlined.
- pgwhalen 2y agoCtrl-F for "Some motivations are as follows" under the "String view with short string optimizations" section here: https://docs.google.com/document/d/12aZi8Inez9L_JCtZ6gi2XDbQpCsHICNy9_EUxj4ILeE/edit#heading=h.gunuqslkwmna https://docs.google.com/document/d/12aZi8Inez9L_JCtZ6gi2XDbQ... Copying here: > Having the 4-byte prefix directly accessible (without indirection through an offset into a separate data buffer) can substantially improve the performance of comparisons returning false. This prefix can be encoded with multi-column hash keys to accelerate aggregations, joins. Sorts would likely also be significantly faster with this representation (experiments would tell for certain) > Certain algorithms (for example “prefix of string” or “suffix of string” — e.g. PREFIX(“foobar”, 3) -> “bar”) can execute by manipulating StringView values only and not requiring any memory copying of large strings. This document was an early proposal for adding what is now called the StringView (and ByteView) types to the Arrow format itself.
- make3 2y agothe first n bytes are likely by far the most often accessed in practices, specifically for sorting & filtering, etc. Storing them inline is likely a huge optimization for little cost.
- NikkiA 2y agoIt's zero cost, since you want the pointer to be 64bit aligned anyway.
- Rygian 2y ago> “short string optimization”: A short enough string can be stored “in place” [...] An optimization that’s impossible in Rust, by the way ;). Author is not aware of https://docs.rs/compact_str/latest/compact_str/ https://docs.rs/compact_str/latest/compact_str/ or https://github.com/bodil/smartstring https://github.com/bodil/smartstring
- diggan 2y agoThat documentation talks about all the benefits and "can mostly be used as a drop in replacement for String", but what are the tradeoffs? When cannot it be used?
- tialaramex 2y agoIt looks like there's a bunch of "garbage collection" type activity where you may have some bytes which were once part of a string but aren't now used, and you're always paying for the overhead of this optimisation even if it's useless for your problem. Suppose you work only with 500-4000 byte strings, maybe they're short reviews, and each ends with a rating in star emoji, ***** is the best * is the worst. [[HN ate my star emoji of course]] So your reviews never fit in the "optimised" string slot, but also the prefix is just opening words from a review, which in some review styles will be the start of seemingly unrelated anecdotes. "My grandfather used to tell me" it'll get to the review eventually, and you'll see why they're connected, but the suffix is useful and that's not stored in a "German string" data structure. Or maybe you have a high turnover of somewhat related medium size strings, so then that garbage collection step costs quite a lot of overhead.
- LegionMammal978 2y agoAny code built closely around String's power-of-2 reallocation pattern may have to be reworked. I don't think there's any case when it cannot be used as a String replacement at all, except maybe when interfacing with an API that expects a &mut String as an output parameter.
- runeblaze 2y agoMy uninformed guess is that at least it will cost you the branching because you need to check if it is inlined or not, and you pay that for every string. Branch prediction is likely very good for this case though.
- deleted 2y ago[deleted]
- Rygian 2y ago> When you access a transient string, the string itself won’t know whether the data it points to is still valid, so you as a programmer need to ensure that every transient string you use is actually still valid. In my mind this reads identical to "if you're a security practitioner, worry about this bit here."
- renewiltord 2y agoHaha, quite a huge improvement in a point-release. 0.20.5 to 0.20.6. This is a cool article. Good motivation. Good explanation. Plots. ~~One small thing is that the plots are missing a legend so I had to hover~~. Nevermind, I don't know why it didn't show (or why I thought that) because I can clearly see them on the x-axis now.
- xiaodai 2y agoFor short strings, this is basically the same concept as ShortStrings.jl in julia https://github.com/JuliaString/ShortStrings.jl https://github.com/JuliaString/ShortStrings.jl
- lmeyerov 2y agoI wonder if something like arrow's custom extension types mechanism would streamline building novel data representations without full forks? It may highlight gaps in the extension mechanism For similar reasons, we've been curious about new compression modes on indexes
- kristianp 2y agoDon't you lose the in-memory interop with other libraries by doing this? I'm thinking that duckdb will no longer be able to read polars data that has been loaded into memory, as it can currently do, due to duckdb supporting Arrow. Isn't the benefit of arrow that it's supported by many languages and libraries as a standard? Will there be an option to use the "compatible" string format?
- emidln 2y agoWouldnt you just recompile your duckdb with the hacked Arrow?
- suremarc 2y agoArrow is a cross-language standard. Polars is written in Rust but DuckDB is written in C++. So it's not that simple unfortunately.
- emidln 2y agoIf you're using Arrow from duckdb, you're using C or C++ bindings. Hack the arrow lib, recompile (and adjust if necessary) whatever bindings/programs using your hacked arrow. If you're using multiple implementations of arrow that arent just bindings, you might have to hack it in more than one place. You don't have to solve the entire world, you only need to hack what you actually use. If the issue with an optimized arrow impl is memory incompat in duckdb, recompile duckdb with your hacked arrow. This is where "overengineered" stuff like mono repos really shine. I've done exactly this type of thing at past jobs. Don't let perfect be the enemy of good enough.
- mau 2y agoArrow supports this string format: https://arrow.apache.org/docs/format/Columnar.html#variable-size-binary-view-layout https://arrow.apache.org/docs/format/Columnar.html#variable-... From the article: > As luck would have it, the Arrow spec was also finally making progress with adding the long anticipated German Style string types to the specification. Which, spoiler alert, is the type we implemented.
- sixtram 2y agoDoes anyone know what tool and font was used in the illustrations in the article?
- Joker_vD 2y ago> As I mentioned above already pre-allocating the required size of data is hard. This leads to many reallocations and memcopy’s during the building of this type. Well. Reallocations have to happen mostly because the virtual memory space is flat, so you can't just grow your allocations without the possibility to accidentally bumping into some other object. But having non-flat virtual memory space is really inconvenient (Segment selectors! CHERI! And what about muh address arithmetic?) for other reasons, so here we are. I toyed with the idea of having a specialized memory allocator for incrementally growing, potentially very large buffers by having it space allocations by, say, 16 GiB, and then there would be the "finalize" operation which would hand over the buffer's contents to malloc by asking malloc to allocate the exact final buffer size (rounded up to the page size) and then, instead of memcpy-ing the data, I'd persuade the OS to remap the physical pages of the existing allocation into the virtual address returned by malloc. The original buffer's virtual addresses then would become unmapped and could be reused. Unfortunately, I couldn't quite persuade the OS to do that with user-available memory management API so it all came to nothing. I believe there was similar research in the early 90s and it failed because it too required custom OS modifications.
- Karellen 2y agoGiven that you're writing a custom allocator, why were you trying to hand allocations over to malloc()? Why not entirely replace malloc() for the process? (If you still need libc malloc for smaller non-growable allocations under the hood, you should be able to privately access it via dlopen()/dlsym() in your code, shouldn't you?)
- Joker_vD 2y ago> why were you trying to hand allocations over to malloc()? So that they could be released with free(). For historical reasons, on Linux, most libraries don't generally provide foo_free() functions to be used for freeing objects returned from those libraries, everyone is supposed to use free(), under the tacit assumption that there is only one version of libc loaded in the process which everyone will use. The Windows world has somewhat better culture in this regard. > Why not entirely replace malloc() for the process? Now that's just rude.
- Kalanos 2y agointeresting. strings was supposed to be one of arrow's big features in comparison to numpy, right?
- sakras 2y agoThey operate in somewhat different domains - numpy is to numerical data as pyarrow is to dataframe data. This means Arrow has strings, maps, nested types, etc. Note that I compared to pyarrow and not Arrow - Arrow refers to the arrangement of bytes in memory and isn’t tied to Python or anything.
- zeristor 2y agoNo mention of byte alignment, am I just thinking too low level for optimisation?
- sakras 2y agoWell, the array of Umbra strings will almost certainly be aligned to 16-bytes, since each string view is a fixed 16 bytes. For the secondary buffer containing long strings, they would not have any particular alignment because they contain bytes, which are 1-byte aligned. Enforcing an alignment for each string would waste a lot of space, and also it's not clear what that alignment would be. For example, if you had a 37-byte side string, what would you align it to?
- mijoharas 2y ago> The huge (in my opinion pathological) downside of the this data type is that the gather and filter operation on this type scale linear in time complexity with the string sizes. Can anyone explain why this is?
- rvilj 2y agoThe length of the buffer for entire column in O(n * k). If you want to gather a subset of the strings in that buffer, you essentially need to scan across the buffer and copy out the subset you want. Because that buffer grows with string size k, it's linear wrt k. The new implementation doesn't have this problem - you only need to deal with views which are constant size.