25 July, 2019

Is C++20 ssize() Broken by Design?

This is a short post in which I would like to raise some concerns regarding std::ssize() (P1227) proposal. Sizes were always represented by [an unsigned] size_t type, which "on many platforms (an exception is systems with segmented addressing) can safely store the value of any non-member pointer, in which case it is synonymous with uintptr_t". This means that the size of size_t equals the size of a machine word on most targets.

I don't think the P1227 proposal was thought through and I believe it's broken by design. The immediate question is whether a 32-bit process can allocate 2^31 bytes of continuous memory and use such memory in a container. The answer is yes it's possible and I have verified it. The next question is how does the proposed std::ssize() implementation deal with that? The answer is undefined behavior as std::ssize() function simply casts its input to ptrdiff_t.

P1227 Motivation

Let's go to the beginning and analyze the sample code of the motivation section in P1227:

template <typename T>
bool has_repeated_values(const T& container) {
  for (int i = 0; i < container.size() - 1; ++i)
    if (container[i] == container[i + 1])
      return true;
  return false;
}

This is the sample code that tries to explain the need for std::ssize() function. The code is wrong at so many levels. It uses int type as an array index, which is signed and won't have a proper size on 64-bit targets. A decent compiler should at least warn about comparison of signed and unsigned values as sizes are normally unsigned. In addition, decrementing one from the size means that the result would wrap around if the container is empty, which is definitely not a border case. I don't think that such example should be used as a foundation in a feature proposal.

P1227 Solution

The proposal also talks about a possible solution by taking advantage of the proposed std::ssize() function, which would return ptrdiff_t, which is simply said a signed version of size_t. There is a problem though, if an array is so large (greater than PTRDIFF_MAX elements, but less than SIZE_MAX bytes), that the difference between two pointers may not be representable as ptrdiff_t, the result of subtracting two such pointers is undefined. This implies that using ssize() is also UNDEFINED when the size of a container is greater than PTRDIFF_MAX, which would be 2^31 - 1 on 32-bit targets.

So finally here is the proposed solution to the problem:

template <typename T>
bool has_repeated_values(const T& container) {
  for (ptrdiff_t i = 0; i < std::ssize(container) - 1; ++i)
    if (container[i] == container[i + 1])
      return true;
  return false;
}

The code definitely fixes the empty container problem, but it adds a possibility for undefined behavior as ptrdiff_t cannot represent all values of size_t.

Undefined Behavior Example

I have written a simple example in which I would like to demonstrate that replacing size_t with ptrdiff_t simply doesn't work:

#include <stdint.h>
#include <stdio.h>
#include <new>
#include <vector>

// A possible implementation of std::ssize(), simplified for our purpose.
static ptrdiff_t my_ssize(size_t size) {
  return ptrdiff_t(size);
}

// The proposed solution in P1227 that uses my_ssize() instead of std::ssize().
template <typename T>
bool has_repeated_values(const T& container) {
  for (ptrdiff_t i = 0; i < my_ssize(container.size()) - 1; ++i)
    if (container[i] == container[i + 1])
      return true;
  return false;
}

int main(int argc, char* argv[]) {
  try {
    // Let's create a vector that has more items than 2^31.
    std::vector<uint8_t> v;
    v.resize(2147484000, uint8_t(0));

    printf("Have a vector of size: %zu\n", v.size());
    printf("Have a vector of ssize: %zi\n", my_ssize(v.size()));

    printf("Has repeated values: %d\n", int(has_repeated_values(v)));
    return 0;
  }
  catch(std::bad_alloc& ex) {
    printf("Bad alloc thrown!\n");
    return 1;
  }
}

Compile the code:

g++ example.cpp -m32 -O2 -std=c++11 -o example

And execute it:

Have a vector of size: 2147484000
Have a vector of ssize: -2147483296
Has repeated values: 0

The output is obviously wrong, the reported size of the container as ptrdiff_t simply doesn't work as the size of the container [2147484000] is not representable in ptrdiff_t. So the proposed solution doesn't work as well as the loop terminates immediately because the value returned by std::ssize() is negative [-2147483296].

Better Solution

If you want to compare pairs in an indexed container then the best is to start from the second index (1) and to compare the previous value with the current one:

#include <stdint.h>
#include <stdio.h>
#include <new>
#include <vector>

// Simple solution.
template <typename T>
bool has_repeated_values(const T& container) {
  for (size_t i = 1; i < container.size(); i++)
    if (container[i - 1] == container[i])
      return true;
  return false;
}

int main(int argc, char* argv[]) {
  try {
    std::vector<uint8_t> v;
    v.resize(2147484000, uint8_t(0));

    printf("Have a vector of size: %zu\n", v.size());
    printf("Has repeated values: %d\n", int(has_repeated_values(v)));
    return 0;
  }
  catch(std::bad_alloc& ex) {
    printf("Bad alloc thrown!\n");
    return 1;
  }
}

The compiled code would work properly regardless of the container size:

Have a vector of size: 2147484000
Has repeated values: 1

Conclusion

I know that the motivation for std::ssize() is ranges support and not a has_repeated_values() function, however, I'm concerned about the trend here. If it's not possible to safely cast size_t to ptrdiff_t then ssize() is broken by design and any code using it is broken including the P1227 solution.