Timeline for Implementation of itoa which allocates the string
Current License: CC BY-SA 4.0
13 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jul 15, 2021 at 19:05 | comment | added | Matthieu M. | @Dev: Eeek! Fixed, thanks. | |
| Jul 15, 2021 at 19:05 | history | edited | Matthieu M. | CC BY-SA 4.0 |
Fair a bit better => Fare a bit better.
|
| Jul 15, 2021 at 18:08 | comment | added | Dev | "fair a bit better" -> "fare a bit better" :) | |
| Jul 15, 2021 at 17:31 | comment | added | Peter Cordes |
I was trying to figure out if there was some use for a rougher inexact count, but if you keep the mallocing API it probably only makes sense if the string does start at the front of the buffer. So you need an exact count, either via a tmp buffer (length for free) and memcpy or ahead of allocation. Perhaps getting some multiply latency into the pipeline before the call to malloc could help some with latency. Using the calculated exact length as a loop termination condition could allow the loop-exit branch prediction to be checked earlier than the x /= 10 dep chain..
|
|
| Jul 15, 2021 at 17:26 | comment | added | Peter Cordes |
You might actually use an API like char *atoi_end(char *buff_end, unsigned x); to avoid needing to count at all (like in the asm Q&A I linked). glibc actually does that internally. But that's probably only useful if you're going to feed it to a syscall (like in the linked asm question) or a function like puts. If you were going to copy without truncating to a fixed length, you'd want to just do a normal atoi to write the digits to their final location.
|
|
| Jul 15, 2021 at 17:24 | comment | added | Peter Cordes |
Storing directly into the destination does nicely avoid store-forwarding stalls which costs latency. Note that out-of-order exec will overlap the num_digits latency with the multiply latency. bsr -> load -> add -> shr is at least 10 cycle latency on an Intel CPU (3 + 5 + 1 + 1), assuming L1d hit for the table. So not 1 ns, but performance of tiny sequences of instructions must be considered as latency and front-end / back-end throughput costs separately, not one-dimensional ns or cycles to add up. (I'd believe that it costs ~1 ns tput vs. a func that formats from the end of a buffer.)
|
|
| Jul 15, 2021 at 17:08 | comment | added | Peter Cordes |
How do I print an integer in Assembly Level Programming without printf from the c library? has some links at the bottom to blogs about fast itoa. (e.g. doing x /= 100 steps and splitting that up, to gain some instruction-level parallelism.) pvk.ca/Blog/2017/12/22/… / tia.mat.br/posts/2014/06/23/integer_to_string_conversion.html
|
|
| Jul 15, 2021 at 17:06 | history | edited | Peter Cordes | CC BY-SA 4.0 |
That millisecond time for free sounds like a worst case, not typical. Also, typo, and link multiplicative inverse details.
|
| Jul 15, 2021 at 13:47 | vote | accept | toni | ||
| Jul 14, 2021 at 15:06 | history | edited | Matthieu M. | CC BY-SA 4.0 |
Remove unnecessary ULL suffix in constants.
|
| Jul 14, 2021 at 14:32 | history | edited | Matthieu M. | CC BY-SA 4.0 |
added 1 character in body
|
| Jul 14, 2021 at 14:15 | history | edited | Toby Speight | CC BY-SA 4.0 |
Spelling and grammar; use real headers
|
| Jul 14, 2021 at 14:05 | history | answered | Matthieu M. | CC BY-SA 4.0 |