vector is slow due to huge array

Discussion in 'C++' started by Nephi Immortal, Nov 11, 2011.

  1. 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.
    Nephi Immortal, Nov 11, 2011
    #1
    1. Advertising

  2. On Nov 11, 1:18 am, Nephi Immortal <> wrote:

    >         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?
    Nick Keighley, Nov 11, 2011
    #2
    1. Advertising

  3. Nephi Immortal

    Arne Mertz Guest

    On Nov 11, 2:18 am, Nephi Immortal <> wrote:
    >         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.
    Arne Mertz, Nov 11, 2011
    #3
  4. Nephi Immortal

    Jorgen Grahn Guest

    On Fri, 2011-11-11, Nephi Immortal wrote:
    > 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

    --
    // Jorgen Grahn <grahn@ Oo o. . .
    \X/ snipabacken.se> O o .
    Jorgen Grahn, Nov 11, 2011
    #4
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Jman

    Slow page load due to viewstate

    Jman, Jan 16, 2007, in forum: ASP .Net
    Replies:
    2
    Views:
    603
    Eliyahu Goldin
    Jan 16, 2007
  2. Replies:
    8
    Views:
    1,876
    Csaba
    Feb 18, 2006
  3. Fresh
    Replies:
    2
    Views:
    609
    Bo Persson
    Apr 22, 2008
  4. Replies:
    3
    Views:
    468
  5. NEtsdpace news
    Replies:
    2
    Views:
    143
    NEtsdpace news
    Sep 29, 2004
Loading...

Share This Page