vector is slow due to huge array

[Nephi Immortal]

I am going to create a huge array even as 100 MB. The problem is
that shift some elements in the right direction after number of
elements are inserted. Vector is slow due to shift issue. Linking
List is not the option because list of pointers take more memory.
I want to know how many elements are limited in order to use shift.
Perhaps, you recommend 4KB, 256KB, or 1 MB. The array of 100 MB is
divided into 4 KB pages or sub-arrays. The list of pointer gets each
page’s memory address.
The program can speed up and run faster if 4 KB pages are used. The
insert and shift can narrow to 4 KB page and leave other pages
untouched. It is an example of string object like word processor.

 

[Nick Keighley]

        I am going to create a huge array even as 100 MB.  The problem is
that shift some elements in the right direction after number of
elements are inserted.  Vector is slow due to shift issue.

yes. If you shift the first element you move 100M.

 Linking
List is not the option because list of pointers take more memory.

        I want to know how many elements are limited in order to use shift.

I think you need to measure. I'm guessing you've implemented this as a
list of vectors (or the moral equivalent). How big the vectors are
only you can answer. You're trading space against speed.
vector.size()==100M is too slow and vector.size()==1 is too big. Run
some tests, maybe on a smaller array. And decide what you find
acceptable.

Perhaps, you recommend 4KB, 256KB, or 1 MB.  The array of 100 MB is
divided into 4 KB pages or sub-arrays.  The list of pointer gets each
page’s memory address.

4k sounds a good place to start then.

        The program can speed up and run faster if 4 KB pages areused.  The
insert and shift can narrow to 4 KB page and leave other pages
untouched.  It is an example of string object like word processor.

and is the size acceptable?

 

[Arne Mertz]

        I am going to create a huge array even as 100 MB.  The problem is
that shift some elements in the right direction after number of
elements are inserted.  Vector is slow due to shift issue.  Linking
List is not the option because list of pointers take more memory.
        I want to know how many elements are limited in order to use shift.
Perhaps, you recommend 4KB, 256KB, or 1 MB.  The array of 100 MB is
divided into 4 KB pages or sub-arrays.  The list of pointer gets each
page’s memory address.
        The program can speed up and run faster if 4 KB pages areused.  The
insert and shift can narrow to 4 KB page and leave other pages
untouched.  It is an example of string object like word processor.

What about using std::deque? Or, if your shifting/insertion has the
same amount
of elements each time, you could make up your own container wrapped
around something
like std::list<std::array<T, CHUNK_SIZE>>.

The size of your pages/chunks/subarrays should approximately match the
size of
a cache line on your system. Lower sizes would give you no performance
gain.

 

[Jorgen Grahn]

I am going to create a huge array even as 100 MB. The problem is
that shift some elements in the right direction after number of
elements are inserted. Vector is slow due to shift issue. Linking
List is not the option because list of pointers take more memory.
I want to know how many elements are limited in order to use shift.
Perhaps, you recommend 4KB, 256KB, or 1 MB. The array of 100 MB is
divided into 4 KB pages or sub-arrays. The list of pointer gets each
page?s memory address.
The program can speed up and run faster if 4 KB pages are used. The
insert and shift can narrow to 4 KB page and leave other pages
untouched. It is an example of string object like word processor.

About 20 years ago when I asked on Usenet about data structures for
text editing, I got the advice to use buffer-gap:

There seems to be a Wikipedia article; I don't know how good it is:
http://en.wikipedia.org/wiki/Gap_buffer

Also check out "The Craft of Text Editing" by Craig A. Finseth:
http://www.finseth.com/craft

It seems to me you need to do something like this; no standard
container would fit your problem.

/Jorgen