interesting. strings was supposed to be one of arrow's big features in comparison to numpy, right?
Why Polars rewrote its Arrow string data type
51–60 of 70 posts
Re: Why Polars rewrote its Arrow string data type
#52Earlier quoted context omitted.
It is not. It is not implemented in std::string::String, but (as pointed out elsewhere in this thread) there are other string implementations that have it. It was decided explicitly against for the standard library, because not every optimization is universally good, and keeping String as a thin wrapper over Vec is a good default.
This is one of those things that I wish people would speak more carefully about. I've seen it in every programming language community I've participated in, so it's not a language-specific thing, but... one should not say "language X does not do a thing" when they mean "language X's standard library does not do a thing". That the "language" doesn't do a thing should be reserved for the cases where the language itself…
Yep, especially with a systems language. As you say, they're basically built for "I need to do something specific."
Re: Why Polars rewrote its Arrow string data type
#53Earlier quoted context omitted.
It is not. It is not implemented in std::string::String, but (as pointed out elsewhere in this thread) there are other string implementations that have it. It was decided explicitly against for the standard library, because not every optimization is universally good, and keeping String as a thin wrapper over Vec is a good default.
When are small strings bad? Parallelism?
Just wanted to say that I only got back to this thread now, but I agree with my sibling commentors.
Here's a discussion about it from a few years back, with some links to the primary discussions: https://news.ycombinator.com/item?id=18372332
Re: Why Polars rewrote its Arrow string data type
#54No mention of byte alignment, am I just thinking too low level for optimisation?
Re: Why Polars rewrote its Arrow string data type
#55No mention of byte alignment, am I just thinking too low level for optimisation?
Well, 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?
Re: Why Polars rewrote its Arrow string data type
#56Earlier quoted context omitted.
It is not. It is not implemented in std::string::String, but (as pointed out elsewhere in this thread) there are other string implementations that have it. It was decided explicitly against for the standard library, because not every optimization is universally good, and keeping String as a thin wrapper over Vec is a good default.
When are small strings bad? Parallelism?
It adds a branch every time you access the string (to check if it is small or not), and can stop various optimisations. g++ used to have small string optimisation, but (eventually) removed it.
Re: Why Polars rewrote its Arrow string data type
#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?
Re: Why Polars rewrote its Arrow string data type
#58> “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/ or https://github.com/bodil/smartstring
That 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?
My 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.
Re: Why Polars rewrote its Arrow string data type
#59interesting. strings was supposed to be one of arrow's big features in comparison to numpy, right?
They 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.
Re: Why Polars rewrote its Arrow string data type
#60> 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?)