Repetitive indexing a std::map with same index

Discussion in 'C++' started by Urs Thuermann, Nov 3, 2011.

  1. I have a case where I must access a std::map using operator[] where
    there is a high probability that the same index is used repetitively
    for a number of times. Will I improve performance when I remember the
    last index used and compare each time I access the map, or are map
    implementations usually optimized for this case?

    I am thinking of something like this (much simplified):

    class Debug {
    pthread_t last_tid;
    struct LineBuffer *last_buf, *line_buf;
    std::map<pthread_t, LineBuffer> map;

    template <class T>
    Debug &operator<<(const T &a) {
    pthread_t tid = pthread_self();
    if (tid == last_tid) {
    line_buf = last_buf;
    } else {
    line_buf = &map[tid];
    last_tid = tid;
    }

    // write 'a' to the line_buf,
    // flush to cerr when complete.
    ;

    return *this;
    }
    };

    so multiple threads can write

    Debug() << "foo value is " << foo << " yadda yadda" << std::endl;

    without having their output mangled with other debug messages.

    urs
    Urs Thuermann, Nov 3, 2011
    #1
    1. Advertising

  2. On 11/3/2011 10:00 AM, Urs Thuermann wrote:
    > I have a case where I must access a std::map using operator[] where
    > there is a high probability that the same index is used repetitively
    > for a number of times. Will I improve performance when I remember the
    > last index used and compare each time I access the map, or are map
    > implementations usually optimized for this case?


    Maybe. But at what cost? How is your cache invalidated?

    > I am thinking of something like this (much simplified):
    >
    > class Debug {
    > pthread_t last_tid;
    > struct LineBuffer *last_buf, *line_buf;
    > std::map<pthread_t, LineBuffer> map;
    >
    > template<class T>
    > Debug&operator<<(const T&a) {
    > pthread_t tid = pthread_self();
    > if (tid == last_tid) {
    > line_buf = last_buf;
    > } else {
    > line_buf =&map[tid];
    > last_tid = tid;
    > }
    >
    > // write 'a' to the line_buf,
    > // flush to cerr when complete.
    > ;
    >
    > return *this;
    > }
    > };
    >
    > so multiple threads can write
    >
    > Debug()<< "foo value is "<< foo<< " yadda yadda"<< std::endl;
    >
    > without having their output mangled with other debug messages.


    I suppose there *can* exist an implementation that caches the last
    accessed value since it's in the same object that should know when the
    cached value needs to be thrown out. I haven't seen one myself yet.
    And I probably would recommend against implementing such a caching
    mechanism outside of 'std::map' since your object does not know what
    happens to the map element in between calls. What if it was removed
    from the map? The pointer is invalidated, and your object hasn't been
    notified...

    V
    --
    I do not respond to top-posted replies, please don't ask
    Victor Bazarov, Nov 3, 2011
    #2
    1. Advertising

  3. Urs Thuermann

    Jorgen Grahn Guest

    On Thu, 2011-11-03, Urs Thuermann wrote:
    > I have a case where I must access a std::map using operator[] where
    > there is a high probability that the same index is used repetitively
    > for a number of times. Will I improve performance when I remember the
    > last index used and compare each time I access the map, or are map
    > implementations usually optimized for this case?


    "Measure" or "read your implementation" seem like valid replies.

    I bet there is no such optimization in real std::map implementations,
    unless you count the positive effect on the data cache of traveling
    the same path through the tree over and over again.

    /Jorgen

    --
    // Jorgen Grahn <grahn@ Oo o. . .
    \X/ snipabacken.se> O o .
    Jorgen Grahn, Nov 3, 2011
    #3
    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. Peter Jansson
    Replies:
    5
    Views:
    6,275
    Ivan Vecerina
    Mar 17, 2005
  2. Replies:
    1
    Views:
    409
    red floyd
    Dec 21, 2008
  3. Thomas J. Gritzan
    Replies:
    6
    Views:
    1,000
    James Kanze
    Dec 22, 2008
  4. James Kanze
    Replies:
    0
    Views:
    1,985
    James Kanze
    Dec 21, 2008
  5. Nikos
    Replies:
    11
    Views:
    218
    Nikos
    Apr 23, 2005
Loading...

Share This Page