3

If I use int index to access a vector element, will it convert the integer to size_t, and then call the operator[](size_t) function? Is there any performance reduction?

Sergey Kalinichenko
  • 714,442
  • 84
  • 1,110
  • 1,523
user1899020
  • 13,167
  • 21
  • 79
  • 154
  • 3
    Profile and see for yourself :) – Borgleader Dec 03 '15 at 13:11
  • 1
    You could measure and find out. – NathanOliver Dec 03 '15 at 13:12
  • What is making you think to a performance reduction ? – Richard Dally Dec 03 '15 at 13:13
  • 1
    You can compare the [generated code](http://goo.gl/PctzCt) for yourself. Of course it will convert it, `v[0]` uses an `int` and obviously that works. – Jonathan Wakely Dec 03 '15 at 13:14
  • In situations where the compiler allows for the possibility that the `int` is negative, there is significant local performance cost to the choice of `int` vs. `size_t` on x86_64 (because sign extend is relatively expensive). Significant local performance difference might or might not be detectable global performance difference. When does the compiler detect that an specific `int` couldn't be negative? In my experience (looking at generated code) sometimes but less often than when it is obvious to a human. – JSF Dec 03 '15 at 13:52
  • When does a compiler detect that negative `int` would cause undefined behavior so the compiler can zero extend instead of sign extending (substituting faster and differently wrong behavior for the undefined behavior)? My understanding is that should happen. Looking at generated code, I haven't seen it. – JSF Dec 03 '15 at 13:56
  • If the compiler decides to zero extend instead of sign extend, `int` may actually be **faster** than `size_t`. In x86_64, copying or computing a 32-bit value into a 64-bit register while zero extending is always at least as fast as the corresponding copy or compute from 64-bit values. In some cases of instruction alignment and/or possible L1-cache misses, the 32 bit copy or compute with zero extend is significantly faster than starting with 64 bit values. – JSF Dec 03 '15 at 14:00
  • @JSF I cannot see your generated code. According to your discription, using unsigned other than int will avoid sign extension. Is it right? – user1899020 Dec 03 '15 at 14:17
  • Consider a function that takes an iterator `it` as input (which is optimized into a pointer in a 64 bit register for the life of the function) then the function computes and uses its own index `n` which might be `int` or `unsigned` or `size_t` then access `it[n]`. The code for `int` is worse than either `unsigned` or `size_t`. In the obscure cases that `unsigned` and `size_t` differ `unsigned` is faster. But then it also uses `it[n+1]`, now both `int` and `unsigned` are worse than `size_t`. If you want to micro optimize that, you need `(it+1)[n]` with `unsigned` – JSF Dec 03 '15 at 14:36

2 Answers2

5

The main difference between int and size_t is that int is signed, while size_t is unsigned. In addition, the two may have different size, because both types are platform-specific and independent of each other.

When the two sizes are the same, conversion from int to size_t is a no-op, so there are no performance implications.

When the size is different, the compiler is smart enough to pass partial or expanded value of int index into operator [] taking size_t with virtually no overhead, because shrinking the size requires a partial load, while expanding the size requires loading zeros for the upper portion. Note, however, that writing zero for the upper portion of the expanded value is not an additional operation, because it replaces copying the upper portion from an index of size_t type.

Therefore, the answer is no, you wouldn't see any performance differences.

Sergey Kalinichenko
  • 714,442
  • 84
  • 1,110
  • 1,523
  • 2
    My profiling results contradict your analysis. This wasn't with newest compilers so maybe some optimization of undefined behavior has improved to fix this effect. Lacking that, the compiler allowed for negative `int` in many situations, so it sign extended instead of zero extended, and in x86_64 sign extend can be much less efficient than zero extend. – JSF Dec 03 '15 at 13:48
  • @JSF Please share your benchmark. Differences as tiny as this one are notoriously hard to benchmark, because the timing is dominated by the actual access to your vector, which depends on performance of hardware cache. – Sergey Kalinichenko Dec 03 '15 at 13:52
  • Sorry, all profiling was of code belonging to my employer. I cannot share any source code, so benchmark results would be meaningless. Almost all my benchmark results **are** as you expected dominated by cache misses on the target data, so a wide range of asm code differences in the generated code all have ZERO impact. It is only by setting all those aside and looking only at cases where the generated code matters that I found sign extend operations significant. – JSF Dec 03 '15 at 14:10
  • Based on profiling results, we use `unsigned` as the data type for indexes instead of either `int` or `size_t`. Our code has far fewer cases than typical code in which the compiler could safely decide to zero extend an `int`. Our code has no cases of any container with over `2**31` elements. (Over `2**32` bytes is common but over `2**31` elements is years away from possible). There are obscure cases where using `unsigned` as an index needs to be tweaked to avoid being slower than `size_t`. But there are far more cases where `unsigned` is a little faster, and those add up. – JSF Dec 03 '15 at 14:18
0

It depends - size_t is platform dependent.

See also: What's the difference between size_t and int in C++?

Community
  • 1
  • 1
Leonardo Herrera
  • 8,388
  • 5
  • 36
  • 66
  • 1
    @erip, what are you asking? – Jonathan Wakely Dec 03 '15 at 13:20
  • The size of the int type also depends on the platform. This answer is misleading. – mabraham Oct 12 '17 at 20:11
  • @mabraham - misleading how? – Leonardo Herrera Oct 16 '17 at 16:38
  • @LeonardoHerrera The question refers to int and size_t. Both are permitted by the standard to have a size that is determined by the implementation, so the consequences of the decision to use either one to index a vector depends on the implementation. The answer only acknowledges that size_t depends on the platform. – mabraham Oct 17 '17 at 19:25
  • I don't know why this question popped up in my reading today, but it sent me to a rabbit hole. I still think this answer is not misleading, and it answers the question "is there a performance penalty by using `int` to access a vector element?" The answer is still "it depends", given that `size_t` is platform dependent and *not* guaranteed to be an unsigned integer! – Leonardo Herrera Jun 08 '18 at 15:41