status-im / nim-stint

Stack-based arbitrary-precision integers - Fast and portable with natural syntax for resource-restricted devices.
Apache License 2.0
82 stars 11 forks source link

Use smaller limb size for small stints #146

Open arnetheduck opened 9 months ago

arnetheduck commented 9 months ago

https://github.com/status-im/nim-stint/blob/master/stint/private/datatypes.nim#L16C8-L16C8 - currently, Word is used for all stint sizes, ie Stint[16] takes 8 bytes on a 64-bit system.

With bit sizes less than the Word size, we should be using the next-power-of-2 approach, ie both stint[15] and stint[16] should take up 2 bytes of space like an int16.

mratsim commented 9 months ago

Is there a benefit though?

For operations, they will be zero-extended to the machine word size, and so far seq[Stint[15]] is not used at all.

arnetheduck commented 9 months ago

Is there a benefit though?

consider array[1024, stint[16]] / openArray[stint[15]] and so on

and so far

the aim is to make the implementation ABI-compatible with _ExtInt in most ways (and efficient in general, which requires the above point to be fulfilled) and thus serve as a 100% replacement / superset for intXX in Nim

mratsim commented 8 months ago

Is ABI compatibility necessary for size > 64?

Because it won't be on big-endian architecture. That goal was abandoned in the rewrite because it's quite noisy on the code flow for no advantage.

arnetheduck commented 8 months ago

Is ABI compatibility necessary for size > 64?

well, _Extint defines an ABI but it's not easily achieved, in particular when passing parameters (due to differences in struct vs extint ABI details in C with regards to register vs stack passing).

That said, this issue is focused on smaller limb sizes for which ABI compatibility is easy to define (round limb size upwards to the nearest power-of-2, up to the pointer size).

arnetheduck commented 8 months ago

big-endian architecture

these practically don't exist anymore, so the focus is on little-endian - the rest can follow if ever there's a usecase.