compare array, map, vector for speed

[bkelly13]

Windows XP Pro, Visual Studio, C++, MFC, No ATL or CLR

We need to access an array of pointers using the following concept:

Int tag;  // 32 bit int
Struct{ int, int, bool } my_struct;
My_struct  *p_info;

  // the critical part is fetching the pointers.
p_info = my_array[ tag ]

Speed takes priority over space. Tag is currently 16 bit integers and may grow to 19 bits. Once the array is populated it never changes. Populating the array is not time critical. Lookup time is critical. Tag values are not contiguous but tend to populate the lower values followed by the higher.

This is an application that runs in a telemetry system and receives the raw data from the remote sources. There will be multiple streams of data at differing rates and up to 20 MHz each. Data arrives in my application as single stream organized as pairs: tag, value. The tag is used to identify the data. The data is saved in various locations according to which stream it belongs to and its type of data. (Hence the structure pointers in the array.) When sufficient data is received, the data is processed, reformatted some, and sent to a display device for real time monitoring.

Which is better: standard array of pointers, std::vector, CArray, or std::map.

So far, from what I have found, I think map is the slowest requiring several lookups to fetch the data item. I don’t know about std::vector, but I do believe that the speed of a standard array is not likely to be beat. But it does take more space. I am tending toward the simple array because you just cannot get any simpler and faster.

Just in case, the system has dual CPUs with quad core (eight cores) and four Gig of memory.


We need to know what a dragon is
before we study its anatomy.
(Bryan Kelly, 2010)

 

[ArkM]

2^19 pointers in pre-allocated ~2MB array (for 32-bit arch) and 4GB memory system - what's a problem? Of course, it's the fastest access solution: direct access with minimal overheads.

See also Kyoto Cabinet NoSQL DB C++ library (extremelly fast and compact tool):
http://fallabs.com/kyotocabinet/
for in-memory DB and timestamp-tag-value data management.