1

I have read that a cache oblivious stack can be implemented using a doubling array.

Can someone please explain how the analysis makes each push and pop have a 1/B amortized I/O complexity?

phs
  • 10,687
  • 4
  • 58
  • 84
Meghana
  • 11
  • 1
  • @Gabe B represents an X byte block of memory that can be read in one IO operation. Think cache-line. So each of the N operations will only require O(1/B) read/write amortized over all N operations. Also, is this homework? – Ze Blob Aug 27 '12 at 02:58

2 Answers2

3

A stack supports the following operations:

  • Push
  • Pop

While these two operations can be performed using a singly-linked list with O(1) push and O(1) pop, it suffers from caching problems, since the stored elements are dispersed through memory. For this approach, we push to the front of the list, and pop from the front of the list.

We can use a dynamic array as our data structure, and push and pop to the end of the array. (We will keep track of the last filled position in the array as our index, and modify it as we push and pop elements).

Popping will be O(1) since we don't need to resize the array.

If there is an extra space at the end of the array, pushing will be O(1).

Problem is when we try to push an element but there is no space for it. In this case we create a new array which is twice as large (2n), then copy each of the n elements over, followed by pushing the element.

Suppose we have an array which is already size n, but starts empty.

If I push n+1 elements onto the array, then the first n elements take O(1)*n = O(n) time.

The +1 element takes O(n) time, since it must build a new copy of the array.

So pushing n+1 elements into the array is O( 2n ), but we can get rid of the constant and just say it is O(n) or linear in the number of elements.

So while pushing a single element may take longer than a constant operation, pushing a large number of elements takes a linear amount of work.

The dynamic array is cache-friendly since all elements are a close to each other as possible, so multiple elements should be in the same cache-lines.

Xantix
  • 3,321
  • 1
  • 14
  • 28
1

I would think standard stacks are cache-oblivious. You fault on only 1/B of the accesses because any sequence of push/pop must be adjacent addresses, so you can hit a new cache line only once every B operations. (Note: argument requires at least 2 cache lines to prevent thrashing.)

Keith Randall
  • 22,985
  • 2
  • 35
  • 54
  • Thank you for the replies. By 'standard' stack, I assume it is meant that the elements are contagious and that is what I agree is precisely achieved by the doubling array technique. The key point is one needs 2 cache lines to prevent thrashing. So is this achieved by assuming optimal page replacement strategy? – Meghana Aug 27 '12 at 16:15
  • @Meghana: that is what is usually assumed for cache-oblivious analysis. But for this problem, assuming just LRU works fine. – Keith Randall Aug 27 '12 at 16:19