Only time will be considered in the following discussion. In the next section these sequence data structures will be compared on a range of criteria. Remember that the ItemAt times assume a very high locality of reference. If the references were not local the ItemAt times would be much higher and the ratios would be different.
The Arr method has the fastest ItemAt but is terrible for Insert and Delete. It is not a practical method.
The Gap method is nearly as fast for ItemAt but is also quite fast for Insert and Delete. The Gap method is a generally fast method but some other problems as will be seen in the next section.
The List method has the fastest Inserts and Deletes by far but a fairly slow ItemAt. The List method uses a lot of extra space (two pointers per item). It is useful for in-memory sequences with large items.
The FsbA method is slow for Inserts and Deletes but its ItemAt can be made quite fast with some simple caching. It is possible to reduce the ItemAt time even further by making it an inline operation. The FsbG method reduces the Insert and Delete times radically but the ItemAt time is a bit higher. The equivalent ItemAt caching would be a little more complicated and a little slower.
The Piece method has excellent Insert and Delete times (only slightly slower than the linked list method) but its ItemAt time is quite slow even with simple caching. More complex ItemAt caching that avoids procedure calls is necessary when using the Piece method. The idea of the caching is simple. Instead of requesting an item you request the address and length of the longest span starting at a particular position. Then all the items in the span can be accessed with a pointer dereference (and increment). This will bring the ItemAt time down to the level of the array and gap methods.