Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Why Polars rewrote its Arrow string data type

pola.rs

Post reply on HN
Print view View original

61–70 of 70 posts

Re: Why Polars rewrote its Arrow string data type

#61

Post by suremarc »

emidln wrote: post #31
kristianp wrote: post #30

Don'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?

Wouldnt you just recompile your duckdb with the hacked Arrow?

Arrow is a cross-language standard. Polars is written in Rust but DuckDB is written in C++. So it's not that simple unfortunately.

Re: Why Polars rewrote its Arrow string data type

#62

Post by NikkiA »

make3 wrote: post #17
ismailmaj wrote: post #7

I might have missed it in the article but I'm not sure why the prefix is stored for strings that can't be inlined.

the 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.

It's zero cost, since you want the pointer to be 64bit aligned anyway.

Re: Why Polars rewrote its Arrow string data type

#63

Post by NikkiA »

o11c wrote: post #15
lor_louis wrote: post #4

Earlier quoted context omitted.

It looks a lot like cedarDB's "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.

Hm, 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 i…

The point of a 12-char short string is that it fits, with the size, into a 16byte cache unit and a single memory transfer on current architectures. Anything else will involve some loss of performance.

As for short strings, they don't have a prefix at all - the 12 bytes simply follow the 4 bytes of the length.

Long strings will need the pointer 64bit aligned, so a 4 byte length means you'd have 4 bytes wasted to the pointer alignment anyway, and you fill those with the preview 'prefix'. dword length + 4 bytes + 64bit address = 16 bytes, again. They both occupy the same space in the cache, and only the data at the other end of a pointer on long strings gets pulled into cache if you decide the prefix matches and you need to follow it.

Re: Why Polars rewrote its Arrow string data type

#64

Post by Joker_vD »

Karellen wrote: post #60
Joker_vD wrote: post #45

> 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 inconvenien…

Given 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?)

> 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.

Re: Why Polars rewrote its Arrow string data type

#65

Post by rvilj »

mijoharas wrote: post #57

> 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?

The 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.

Re: Why Polars rewrote its Arrow string data type

#66

Post by emidln »

suremarc wrote: post #61
emidln wrote: post #31

Earlier quoted context omitted.

Wouldnt you just recompile your duckdb with the hacked Arrow?

Arrow is a cross-language standard. Polars is written in Rust but DuckDB is written in C++. So it's not that simple unfortunately.

If 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.

Re: Why Polars rewrote its Arrow string data type

#67

Post by Karellen »

Joker_vD wrote: post #64
Karellen wrote: post #60

Earlier quoted context omitted.

Given 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?)

> 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…

> So that they could be released with free().

Well, yes, you have to replace free() and calloc()/realloc() too. Sorry, didn't think that needed spelling out.

> > Why not entirely replace malloc() for the process?

> Now that's just rude.

Isn't that generally what alternate custom allocators do, though? Like dmalloc and jemalloc?

Re: Why Polars rewrote its Arrow string data type

#68

Post by Joker_vD »

Karellen wrote: post #67
Joker_vD wrote: post #64

Earlier quoted context omitted.

> 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…

> So that they could be released with free(). Well, yes, you have to replace free() and calloc()/realloc() too. Sorry, didn't think that needed spelling out. > > Why not entirely replace malloc() for the process? > Now that's just rude. Isn't that generally what alternate custom allocators do, though? Like dmalloc and jemalloc?

Well, it's one thing when you, as an author of a program, links libraries into your code, and then you pick a custom allocator, and then the libraries you've picked will (transparently) use it. It's an altogether different thing when you, an author of a library, decide to use a custom allocator and then, since your users probably can't be persuaded to use your custom foo_free() that you could export, you hijack the libc's malloc implementation from anyone who links against you and replace it with your own. I personally think it's just rude.

So, with those constraints it's either memcpy-ing into the buffer that you get from the global malloc(), or trying to remap the addresses that that buffer spans onto your own buffer; I thought the latter could be faster starting with moderately large buffers but since I couldn't make it work, I couldn't benchmark it so nothing came out of it.

Re: Why Polars rewrote its Arrow string data type

#69

Post by Karellen »

Joker_vD wrote: post #68
Karellen wrote: post #67

Earlier quoted context omitted.

> So that they could be released with free(). Well, yes, you have to replace free() and calloc()/realloc() too. Sorry, didn't think that needed spelling out. > > Why not entirely replace malloc() for the process? > Now that's just rude. Isn't that generally what alternate custom allocators do, though? Like dmalloc and jemalloc?

Well, it's one thing when you, as an author of a program, links libraries into your code, and then you pick a custom allocator, and then the libraries you've picked will (transparently) use it. It's an altogether different thing when you, an author of a library, decide to use a custom allocator and then, since your users probably can't be persuaded to use your custom foo_free() that you could export, you hijack the l…

Ah.

One other approach that does occur is to just malloc() a 16GiB buffer to begin with. Only pages you touch should end up being backed by RAM(/swap). Then your finalize() operation is just a realloc() to "shrink" the buffer down to its final size. Any decent allocator should keep the data where it is, and just make the now-unused tail portion of address space available again, without ever having needed to back it.

Re: Why Polars rewrote its Arrow string data type

#70

Post by Joker_vD »

Karellen wrote: post #69
Joker_vD wrote: post #68

Earlier quoted context omitted.

Well, it's one thing when you, as an author of a program, links libraries into your code, and then you pick a custom allocator, and then the libraries you've picked will (transparently) use it. It's an altogether different thing when you, an author of a library, decide to use a custom allocator and then, since your users probably can't be persuaded to use your custom foo_free() that you could export, you hijack the l…

Ah. One other approach that does occur is to just malloc() a 16GiB buffer to begin with. Only pages you touch should end up being backed by RAM(/swap). Then your finalize() operation is just a realloc() to "shrink" the buffer down to its final size. Any decent allocator should keep the data where it is, and just make the now-unused tail portion of address space available again, without ever having needed to back it.

It's possible, absolutely, but if you allocate N such fragments one after another, do some allocations in them, and then finalize them from first to the last, there will be gaps left less than 16 GiB in size, so they could only be reused for small allocations; and IIRC allocators with special support for huge allocations (e.g. using so-called huge pages) do not reuse that memory for "normal-sized" allocations (although I can be wrong on this).

So it's a tradeoff: this fragmentation is not that bad but it's still noticeable in a sufficiently long-running program because 16 GiB is 2**34 so you only can make 16 Ki such allocations before you hit the 2**48 limit. And if you could just simply remap them!..

Post reply on HN