“In-place” might be less in-place than you think

The intuitive view of algorithms that work in-place is that (it sounds obvious) they don’t use any extra space. Canonically in C/C++ we think of something like reversing an array, or that interview staple, removing spaces from an ASCII string, which we might write as:

int remove_spaces(char *s)
{
  char *readptr = s;
  char *writeptr = s;
  while (*readptr)
  {
    if (!isspace(*readptr))
    {
      *writeptr++ = *readptr++;
    }
    else
    {
      ++readptr;
    }
  }
  *writeptr = 0;
  return writeptr - s;
}

But “in-place” has a technical definition that is actually more relaxed than using no extra space, because this intuitive sense is too limiting under a formal analysis. As Wikipedia says:

In computational complexity theory, in-place algorithms include all algorithms with O(1) space complexity, the class DSPACE(1). This class is very limited; it equals the regular languages.[1] In fact, it does not even include any of the examples listed above.

For this reason, we also consider algorithms in L, the class of problems requiring O(log n) additional space, to be in-place.

And in the recent book From Mathematics to Generic Programming by Alexander Stepanov (original author of the STL) and Daniel Rose, page 215 offers the definition:

An algorithm is in-place (also called polylog space) if for an input of length n it uses O((log n)k) additional space, where k is a constant.

(I highly recommend the book, by the way.) If you’re only used to thinking about “in-place” intuitively, you could probably be persuaded that using constant extra space is admissible – after all, one probably has to use a few stack variables – but I think the idea that an algorithm is entitled to call itself “in-place” if it uses logarithmic extra space might be surprising. But that’s the technical definition; an author is entitled to call his or her algorithm “in-place” even though it uses O(log n) extra space (and includes the requirement to allocate that space).

3 comments

  1. That seems a little dishonest!

    It’s ironic that these terms (and big O notation) seem to try to abstract away details of the machine you are working on to get to some core values or truths to be able to compare algorithms. They do end up making assumption about the type of machine you are working on though. In this case, that small amounts of memory is free, which may not be the case if you are on some exotic device.

    This sort of stuff is a reason I’ve never really been into big O notation… it is helpful as a general guide, but it doesn’t account for cache coherency, disk access times, etc, so an algorithm could look fine on paper, but be terrible when implemented.

    I’m sure that’s not a popular opinion though and might make me look ignorant to people who disagree (:

  2. I think an example might help build the intuition around why we want “in-place” to mean “logarithmic extra space”. Consider an algorithm that finds an element in a forward range (not sure whether this code will be readable):

    template
    IteratorType find(R seq, ValueType elem) {
      using I = IteratorType(R);
    
      I it = begin(seq);
      while (it != end(seq)) {
        if (*it == elem) return it;
        ++it;
      }
    
      return it;
    
    }
    

    Now, let’s assume that seq has $N-1$ different elements in it. Our iterator it can take on $N$ different possible values, then (it can point to every element in the seq, as well as a one-past-the-end value). This means the iterator will occupy $\log_2(N)$ bits of memory. The in-place definition captures the intuition that we can store some fixed number of iterators (i.e., $\log_2(N)^k$ bits of memory).

    It may seem like we could pick $N$ large enough so seq occupies all addressable memory—if we could never have a seq larger than available memory, $N$ would be constant, so $\log_2(N)^k$ would also be constant. This is very tempting, but our find algorithm says nothing about every element of seq needing to live in memory at the same time. On a 32-bit machine, this limits the amount of information we can process as a sequence to 4 GB—we can’t even search through a DVD, which can store and perform random access on just under 5 GB. Often it’s to pretend $N$ is constant, but sometimes it’s not. The caller will know, but the algorithm will not.

    To address the above comment, one of the great strengths of Generic Programming in this way is that you are abstracting away algorithms in a way that you can still reason about what the machine is actually doing. At the caller side, for instance, we probably have the information whether the elements of seq live in memory or not, and thus whether I can be stored without heap allocation. For instance, if seq of type R is really a std::vector, all elements live in memory, and so I—that is, std::vector::iterator—can have constant size, at least sizeof(std::size_t). Thinking of “in-place” as “can allocate a fixed number of iterators”, we can know the algorithm doesn’t need to go off to the heap to allocate anything, and all iterators can be stored on the stack (thread-locally, so we don’t have to worry about cache-coherency, and they will probably be hot in cache as well). On the other hand, if we make a range dvd::seeker, we can choose the size of the iterator to be 64-bits, a double word. Arithmetic may be slower, but we haven’t lost correctness. In short, our find works on any type imaginable, and is just as efficient as if you had hand-written it for that type. (And, if we have a better way to write the algorithm itself, we can specialize find.)

    Hope this helps readers get a little intuition for why we call something “in-place” when it doesn’t take a constant amount of extra space.

    Cheers,

  3. This definition of in-place allows Quicksort to be considered in-place. The maximum depth of the recursion stack for Quicksort is O(log N).

Leave a comment

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.