Repetitive indexing a std::map with same index

[Urs Thuermann]

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

 

[Victor Bazarov]

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

 

[Jorgen Grahn]

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