[QUESTION] support custom types (i256)

[spebern]

Question

What is the best way of using the lexical optimized parsing routines for
a custom type (arbitrary size integers e.g. 256bit)?

Background:
In arrow the decimal type uses an underlying i256 (https://github.com/apache/arrow-rs/blob/7bf7ea5e341c15dbd8653b16413459f5fa4784eb/arrow-buffer/src/bigint.rs#LL26-L29C2). However, lexical only
supports the rust native types (as far as I understand it). What is the best
way of parsing into arbitrary size integers/byte arrays using lexical?

Thanks!

[Alexhuszagh]

Let me think about a good way to do this: we might be able to use 2 128-bit high/low values and parse from there, since multiplication and addition is quite easy like that. We'd have to benchmark the performance. Is there still interest in this? I could add a i256 feature.

Ideally, this would be done internally with a custom i256 type.

[spebern]

I am not working on anything related to arrow currently, but lexical is still being used there. Maybe @tustvold as a maintainer of arrow can answer this. This was related to a pull request: apache/arrow-rs#3854

[Alexhuszagh]

Sounds good this seems like a very doable request so I'll put it as an enhancement after our release later this week.

[Alexhuszagh]

I'm making serious progress on this, sorry for the delay but we have most of the base logic and then we can implement the parsing logic quite easily into this.

[Alexhuszagh]

I've got the higher order integers, which I needed to optimize from other big integer implementations here. It's got very efficient multiplication and division, especially with scalars, which since we'll be breaking these operations into groups of 19 digits lets us do this very efficiently.

For example, multiplying u256 * u256 is ~2ns on my machine, but u256 * u64 is ~1ns, and this is true no matter the size of the value. So, if we're processing ~75 digits (78 is the max for a 256-bit integer), we can break that into 4 chunks of u64, which would make the overhead of big integer operations much less prohibitive.

This is especially true for division, where I've decreased the time from ~150ns from other libraries (in bad cases, these can even go to ~400us) to ~7ns (slow for integer operations, but not unworkably so, and highly optimal cases can go down to ~2ns), which means all the base logic should be there.

I'll then implement it for the types present, add some benchmarks, and we'll go from there.