Allocating three times the size of the input seems excessive.

[SimonSapin]

The Encoding::decode_* methods need in some cases to allocate a String, and decide how much capacity to give it. Other than *_without_replacement (2984a8b#commitcomment-20990260), this is based on Encoding::max_utf8_buffer_length which assumes the worst case. For many encodings, that’s when every byte of the input is an error that emits a three-byte U+FFFD code point.

In short, as soon as there’s an error, these method allocate three times the size of the (remaining) input. Assuming the worst case simplifies the code which only needs to allocate once, but it seems excessive that a single bit flip near the beginning of the input could triple memory usage.

So a more adaptive allocation scheme might be desirable, but admittedly there is no obvious answer as to what it should be.

[hsivonen]

In short, as soon as there’s an error

It's worse than that for non-UTF-8 encodings. In those cases, it "as soon as there's non-ASCII".

So a more adaptive allocation scheme might be desirable, but admittedly there is no obvious answer as to what it should be.

The obvious choice would be to switch from "as soon as there's non-ASCII" to "as soon as there's an error", which would result in at most one reallocation, but you indicate you'd consider even that excessive.

So a more adaptive allocation scheme might be desirable, but admittedly there is no obvious answer as to what it should be.

One option would be to do the allocation computation for the no-error case plus three (to allow one error to avoid badness when the last byte is in error) and reallocate with that kind of calculation again if the buffer fills up. That could lead to many allocations in the pathological case of the input being full of single-byte errors.

[SimonSapin]

One option would be to do the allocation computation for the no-error case plus three (to allow one error to avoid badness when the last byte is in error) and reallocate with that kind of calculation again if the buffer fills up. That could lead to many allocations in the pathological case of the input being full of single-byte errors.

Right. To avoid O(n²) pathological cases, something like Vec typically uses some exponential growth factor. But here we have an upper bound. So for example if the upper bound 3× size of input, the first allocation could be 1.1×, then if that’s insufficient 2×, then if that’s insufficient again use the upper bound.

But what bothers me about this approach is that I totally pulled the 1.1× and 2× factors out of thin air. And what factors would work better depend a lot on the kind of input being processed. (What encoding, what human language/writing system, what markup language if any, …)

So maybe I shouldn’t worry about it, and 3× over-allocation isn’t that bad for a high level API. A user of this library can always choose use Decoder::decode_to_string instead of Encoding::decode and manage re-allocations themselves.

Feel free to close this issue :)

[hsivonen]

How about this?

First allocate for the no-error case rounded up to the next power-of-two (since jemalloc uses power-of-two buckets, so with jemalloc, the rounding up is for free) and if the buffer turns out to be too small, allocate for the worst case. This would result in at most one reallocation but would avoid useless 3x allocation in the common case.

The encode case already uses jemalloc-optimized rounding up.

[SimonSapin]

jemalloc uses power-of-two buckets

I’m having trouble finding precise docs, but it looks like there are more bucket sizes in-between powers of two: https://blog.mozilla.org/nnethercote/2011/08/05/clownshoes-available-in-sizes-2101-and-up/

[hsivonen]

I’m having trouble finding precise docs, but it looks like there are more bucket sizes in-between powers of two

Whoa. I've somehow managed to miss that. Thanks.

Sadly, RawVec doesn't appear to have machinery to round up to jemalloc buckets, which is disappointing. Rounding would belong there, not here...

[hsivonen]

Since RawVec doesn't know about jemalloc buckets and would on its own grow by a factor of two, rounding to power-of-two isn't far off from the default behavior. However, if such rounding would exceed the length given by max_utf8_buffer_length() the new code uses max_utf8_buffer_length().

It would be nice for RawVec to know how to fill jemalloc buckets exactly, though.

[hsivonen]

Published to crates.io as encoding_rs 0.5.0.