[Bug 2545] performance on std::map

[bugzilla at busybox.net]

https://bugs.busybox.net/show_bug.cgi?id=2545

--- Comment #3 from Nuno Goncalves <nunojpg at gmail.com>  ---
Sorry, I didn't provide that much information in fact.

The elements of class std::map<port_spec, service_node> service_table are:

struct port_spec {
  int portno; /* Network byte order */
  std::string proto;

  /* Sort in the usual nmap-services order. */
  bool operator<(const port_spec& other) const {
    if (this->portno < other.portno)
      return true;
    else if (this->portno > other.portno)
      return false;
    else
      return this->proto < other.proto;
  }
};

/* This is a servent augmented by a frequency ratio. */
struct service_node : public servent {
public:
  double ratio;
};


It will take up to 65536 elements.

I checked on http://cxx.uclibc.org/faq.html:

A deque needs only 3 pointers and a size parameter (essentially 4 integers) to
manage itself. Compare this with at least 2 pointers per item for a tree. After
two items, the memory overhead of the map already outweighs that of the deque.
Also, deque lookups may be faster as moving to the next level in the search
does not require indirection. On the down side, a deque does not resize cleanly
like a map does. It will use more memory than needed in buffering, and will
occasionally need to copy all of the elements to a new container for more free
space. Inserts also execute in O(n) time instead of O(log(n)) time on a deque
unless they are to be added to the front or back of the deque, at which point
they are inserted in O(1)+ time. Lookups and updates are O(log(n)) on both
systems. In the end, I thought that the memory usage of the system outweighed
the performance issues involved. 

Does this mean this is a intrinsic performance problem to save memory? I must
always use the standard libstdc++?

-- 
Configure bugmail: https://bugs.busybox.net/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
You are on the CC list for the bug.