how to convert unsigned char* to integer fast,

Question

In my project i wrote such function for conversion:

    // len should be > 0
uint32_t stringToInt(unsigned char const* buffer, int len) {
    uint32_t result = buffer[0] - '0';
    for (int i = 1; i < len; i++) {
        result *= 10;
        result += buffer[i] - '0';
    }
    return result;
}

Are there any stl / boost methods that can do the same with the same speed? If not so then probaly you can further improve my version?

I can not use atoi because it doesn't allow to provide len. I also don't want to create temp buffer just for atoi call.

I don't think you can get better than linear time with this kind of conversion. — , May 01 '13 at 19:16
If you're looking to squeeze milliseconds out of this then perhaps loop unrolling would help. — john, May 01 '13 at 19:18
As far as I know all string to integer conversions in both `C` and `C++` assumes that you want to convert the whole string. — Ahmed Jolani, May 01 '13 at 19:19
How robust does this need to be? Will check for 0-length buffers? skip extra leading zeroes? check for uint32_t overflow, etc.? — Brett Hale, May 01 '13 at 19:55
@BrettHale no need to be robust at all, input is always valid. — Oleg Vazhnev, May 01 '13 at 19:59
@AhmedJolani: but they also assume the string is null terminated, whereas this code can parse a substring of a larger string — Mooing Duck, May 01 '13 at 20:21
@MooingDuck that's exactly what I did in my solution, I used this trick. — Ahmed Jolani, May 01 '13 at 20:28

score 2 · Accepted Answer · edited May 23 '17 at 11:43

2

From atoi implementation in C, with minor modification to account for length.

int my_atoi(char *p,int len) {
 int k = 0;
 for (int i=0;i<len;i++) {
 k = (k<<3)+(k<<1)+(*p)-'0';
 p++;
 }
 return k;
}

If you want the fastest possible atoi implementation, one way to go would be to check gcc source for their implementation of atoi and modify it to match your additional requirement for length...

edited May 23 '17 at 11:43

Community

1
1

answered May 01 '13 at 19:57

Ilya Kobelevskiy

5,245
4
24
41

I scoffed at this, this is obviously just doing micro-optimizations the compiler ought to be doing already, but then to my surprise [it was faster, though only barely outside my margin of error](http://coliru.stacked-crooked.com/view?id=b31719a1ec9364f2175349f0f6333eb5-50d9cfc8a1d350e7409e81e87c2653ba) Though oddly, having the `result *= 10;` on it's own line seems to make things faster for reasons I didn't understand. – Mooing Duck May 01 '13 at 21:09
Nice comparison! I thought optimizations won't give much speed either - main point of answer was to go from known efficient atoi implementation - this one was the first that appeared in google. Now I'm very curious to see how is it actually implemented in gcc/other modern compiler... – Ilya Kobelevskiy May 01 '13 at 21:16
I've been told over and over and over that such optimizations are a bad idea because the compiler can already do them, I'm just flabbergasted at the results I'm seeing here :( – Mooing Duck May 01 '13 at 21:20
@MooingDuck, you might get different results if everything were `unsigned`. – Mark Ransom May 01 '13 at 22:31
@MarkRansom: When I changed the `int`s to `unsigned`, I got similar results, this answer being ~5% faster than the others. Changing the `chars` to `unsigned char` got a completely unrelated test to the same speeds :/ http://coliru.stacked-crooked.com/view?id=ecbdfb9af178d2170c4a95b71ef49e1e-50d9cfc8a1d350e7409e81e87c2653ba – Mooing Duck May 01 '13 at 22:45
@MooingDuck: I believe version 1 and version 2 of your program actually has identical code. The peephole optimizer probably recognized that in the generated binary, and the instruction cache is primed when you run version 2. If you move version 2 to run last, I think you will see a different time (at least I did on my system). – jxh May 02 '13 at 07:31
@user315052: I expected most of these to have identical code. To prevent cache being an issue, I run each one 1000 times before doing any timings, so all timings should be primed. But since you say you witnessed otherwise, then that is something to consider too. – Mooing Duck May 02 '13 at 15:50

score 0 · Answer 2 · answered May 01 '13 at 19:35

0

Saw this one years ago. Its probably slower but more fun:

int stringToInt(char *buffer, int len) {
    if (len > 0) {
        return myStoi(buffer + len - 1, len);
    }
    return 0;
}

int myStoi(char *curr, int len) {
    if (--len) {
        return myStoi(curr-1, len) * 10 + (*curr - '0');
    }
    return (*curr - '0');
}

This, like the original, assumes the buffer contents are valid digit characters. (i.e. no leading spaces or dashes or plus-signs, no internal dots or alpha chars)

answered May 01 '13 at 19:35

Lee Meador

12,829
2
36
42

1

His version is even faster than this recursive version, the stack popping and pushing give an extra overhead, during programming contest it's always better to write a recursive in an iterative style. – Ahmed Jolani May 01 '13 at 19:38
No disagreement here. But mine is more **fun** – Lee Meador May 01 '13 at 19:41
@AhmedJolani - the code generated for a tail-recursive algorithm by an optimizing compiler may surprise you. That said, you're right that it's really just a curio. – Brett Hale May 04 '13 at 14:12

how to convert unsigned char* to integer fast,

2 Answers2