52 PDeque

PDeque 1

Implementation

Page            Page* m_prev;
                Page* m_next;
                vector<T> m_elements;

PQueue          Page* m_first;
                Page* m_last;
                ssize_t m_size;

iterator        Page* m_page;
                ssize_t m_index;

This allows for fast pushing and popping from both ends because the first and last pages can be partially full.

In fact insertion and erasure from the middle of the queue is quite fast because pages are variable size. A concept of splitting or merging pages is used. When insertion into a page would cause it to reach an upper threshold it is split. When erasure would cause the combined size of two adjacent pages to drop below (twice) a lowest threshold they are merged.

operator[](ssize_t i) requires iteration through pages and therefore is not particularly fast unless i is close to the start or end of the list. Note that the implementation tests i to iterate from the appropriate end.

Iteration in either direction is very efficient. Iterators can be subtracted. Shifting an iterator by an integer offset requires iteration through the pages.

PDeque 2

Page            vector<T> m_elements;

PQueue          vector<Page*> m_pages;
                ssize_t m_size;

iterator        ssize_t m_index;

Pages have a fixed size except the first and last pages. Therefore deletion/insertion into the middle is slow. Push or pop at the ends is fast because these pages can be partially full.

Pages are indexed in a vector. This, combined with the fixed size of most pages allows for operator[] to be fast. However if the number of pages becomes very large then the PDeque object becomes very large.

Support for asynchronous deletion and cloning

A PDeque may become extremely large and therefore may need to be deleted asynchronously. To allow the PersistStore framework to do this automatically the PDeque must be regarded as a tree structure.

One option would be for the PDeque to be the root, and all the pages are the immediate children. However VisitPrefs() would need to visit all the pages, making it very slow. Also, the DeletionQueue would become very large when all the OIDs of the pages are pushed.

                    PDeque
                     /  \
            ---<----/    \--->---
           /                     \
 (first)  /                       \ (last)
         /                         \
      Page  -->-- Page  ...  -->-- Page
            --<--           --<--

Instead the PDeque is regarded as a tree where the PDeque is the parent of the first page, and each page is the parent of the next page in the chain. VisitPrefs() is implemented under this assumption.

            PDeque
               \
               Page  (first page)
                 \
                 ...
                   \
                  Page  (last page)

Problem with embedding persistent data types

We went through the process of converting the PDeque to be plain old data type that could be embedded by value in a container persistable. The problem we found with this approach was that the PushBack function couldn't mark itself as dirty, so we decided to require that the client call MarkAsDirty() on the IPersistable that embedded the PDeque. However since MarkAsDirty always does a trace, that was way too slow, so we considered only calling MarkAsDirtyWithoutTrace but that wouldn't work because sometimes new pages get created and they need to be given oids. So then we gave up and reverted back to the code below. It seems that writing persistent things as embeddable isn't a good idea if they use internal persistable objects (such as the Page below).

todo

• Allow for erase at any position
• Provide range iterator concept
• Ensure marking as dirty calls are efficient
• Implement operator[]
• Allow for range to be efficiently transferred between PDeques
• Investigate options for factorising code to avoid template bloat. E.g. use VectorOfByte?
• Support stack
• Investigate options for fixed sized pages or variable sized pages
• Allow for split and merging of pages

PDeque as a stack

The PDeque supports push_back(), back() and pop_back() allowing it to be used as a efficient stack. Consider the case of a sequence of push, pop calls that cause the last page to repeatedly transition between non-empty and empty. For efficiency we do not want to continually allocate and delete the last page. Therefore we support an empty page at the end of the PDeque. Similarly at the front of the PDeque.

Proposal: avoid such a big macro

We should refactor the code so that most of the code is using normal C++ templates and can be unit tested. That code should be moved into a non-Xcpp library. Somehow this would provide the hooks as needed to support persistence. That would allow the macro to be much smaller. The same is true for our B+Tree implementation - which currently also uses a huge macro.

PDeque.h

Source: Ceda/cxPersistStore/PDeque.h