Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.c++ > #118698
| From | Michael S <already5chosen@yahoo.com> |
|---|---|
| Newsgroups | comp.lang.c++ |
| Subject | Re: std::map advocacy |
| Date | 2024-04-08 11:15 +0300 |
| Organization | A noiseless patient Spider |
| Message-ID | <20240408111535.0000477e@yahoo.com> (permalink) |
| References | (8 earlier) <uurm8q$24ka4$1@dont-email.me> <20240407160050.00004370@yahoo.com> <uuu98b$2qou0$1@dont-email.me> <20240407183854.00000797@yahoo.com> <uuum1i$2tk05$4@raubtier-asyl.eternal-september.org> |
On Sun, 7 Apr 2024 19:44:18 +0200 Bonita Montero <Bonita.Montero@gmail.com> wrote: > Am 07.04.2024 um 17:38 schrieb Michael S: > > > Factor of 5-10 (mentioned in my other post) is quite rare and mostly > > applies not to std::map vs custom implementation of RB or AVL tree, > > ... > > That's nonsense. If the tree type is the same the performance is the > same. The high overhead of a tree comes from the pointer chasing while > looking up a certain node. The issue is the same for manual implemen- > tations. What exactly is nonsense? You are saying approximately the same that I said above. > What could make a map slow is the memory allocation part, but you > could either chose a fast allocator like mimalloc or use a C++23 > flat_map, where insertion or removal is as fast as possible. > I didn't look at flat_map yet. I hate to leave leading edge of the language. In the case that I described in the other post allocation was solved by extract() and pool of nodes. Worked great because in this particular application there were a lot of insertions and deletions, but they perfectly balanced each other and total size of multiset remained constant (+-1) for majority of its life time. > > In this case I happened to have enough time to rewrite it in C with > > my own implementation of AVL tree. My own code was only some 10 or > > 15% faster than std container's. ... > > I also prefer AVL-trees over RB-trees for the faster lookup, Since my application was very modification-intensive, from algorithmic perspective AVL is probably slightly worse than RB. I did AVL not because of algorithmic superiority, but because I understand it better. > but if > the type of tree is the same and the memory allocation part is the > same there should be no performance difference between a manual C > -implementation and a std::map. > In my particular case of 2K to 10K nodes it was indeed almost the same. But for bigger size, e.g. 1M to 10M, manual implementation could be significantly faster, because nodes could be made significantly smaller, improving cache hit rates. That applies to set/multiset more than to map/multimap and to small keys more than to big keys. On x86-64 with MSVC/gcc/clang each std::set/multiset node occupies 32 bytes even when key is only 32 bits. With manual code+custom allocator+ knowledge that size of set never exceeds 4G nodes, the size of node could be reduced to 16 bytes, still with 2 or 3 bytes to spare. Whether it makes significant difference in speed or not, depends on exact size of your set, on your hardware, on your access pattern, etc... But it surely *could* make a difference.
Back to comp.lang.c++ | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread
Ain't that beautiful ? Bonita Montero <Bonita.Montero@gmail.com> - 2024-04-04 20:11 +0200
Re: Ain't that beautiful ? Michael S <already5chosen@yahoo.com> - 2024-04-04 21:55 +0300
Re: Ain't that beautiful ? Sam <sam@email-scan.com> - 2024-04-04 20:00 -0400
Re: Ain't that beautiful ? scott@slp53.sl.home (Scott Lurndal) - 2024-04-05 00:21 +0000
Re: Ain't that beautiful ? Michael S <already5chosen@yahoo.com> - 2024-04-05 17:44 +0300
Re: Ain't that beautiful ? Bonita Montero <Bonita.Montero@gmail.com> - 2024-04-05 17:27 +0200
Re: Ain't that beautiful ? Michael S <already5chosen@yahoo.com> - 2024-04-05 18:37 +0300
Re: Ain't that beautiful ? Bonita Montero <Bonita.Montero@gmail.com> - 2024-04-05 18:04 +0200
Re: Ain't that beautiful ? "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2024-04-06 15:55 -0700
Re: Ain't that beautiful ? Bonita Montero <Bonita.Montero@gmail.com> - 2024-04-07 08:28 +0200
Re: Ain't that beautiful ? scott@slp53.sl.home (Scott Lurndal) - 2024-04-07 15:51 +0000
Re: Ain't that beautiful ? Bonita Montero <Bonita.Montero@gmail.com> - 2024-04-07 19:35 +0200
Re: Ain't that beautiful ? "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2024-04-07 12:21 -0700
Re: Ain't that beautiful ? Bonita Montero <Bonita.Montero@gmail.com> - 2024-04-05 05:05 +0200
Re: Ain't that beautiful ? Michael S <already5chosen@yahoo.com> - 2024-04-05 17:52 +0300
Re: Ain't that beautiful ? Bonita Montero <Bonita.Montero@gmail.com> - 2024-04-05 17:26 +0200
Re: Ain't that beautiful ? scott@slp53.sl.home (Scott Lurndal) - 2024-04-05 20:00 +0000
Re: Ain't that beautiful ? Bonita Montero <Bonita.Montero@gmail.com> - 2024-04-05 22:29 +0200
Re: Ain't that beautiful ? scott@slp53.sl.home (Scott Lurndal) - 2024-04-05 21:29 +0000
Re: Ain't that beautiful ? Bonita Montero <Bonita.Montero@gmail.com> - 2024-04-06 09:06 +0200
Re: Ain't that beautiful ? Paavo Helde <eesnimi@osa.pri.ee> - 2024-04-06 17:29 +0300
Re: Ain't that beautiful ? scott@slp53.sl.home (Scott Lurndal) - 2024-04-06 14:56 +0000
Re: Ain't that beautiful ? Bonita Montero <Bonita.Montero@gmail.com> - 2024-04-06 18:34 +0200
Re: Ain't that beautiful ? wij <wyniijj5@gmail.com> - 2024-04-07 03:00 +0800
Re: Ain't that beautiful ? Bonita Montero <Bonita.Montero@gmail.com> - 2024-04-07 08:28 +0200
Re: Ain't that beautiful ? wij <wyniijj5@gmail.com> - 2024-04-08 07:47 +0800
Re: Ain't that beautiful ? Michael S <already5chosen@yahoo.com> - 2024-04-07 15:25 +0300
Re: Ain't that beautiful ? Michael S <already5chosen@yahoo.com> - 2024-04-07 16:00 +0300
Re: Ain't that beautiful ? David Brown <david.brown@hesbynett.no> - 2024-04-07 16:06 +0200
Re: Ain't that beautiful ? Michael S <already5chosen@yahoo.com> - 2024-04-07 18:37 +0300
Re: Ain't that beautiful ? scott@slp53.sl.home (Scott Lurndal) - 2024-04-07 15:58 +0000
Re: Ain't that beautiful ? David Brown <david.brown@hesbynett.no> - 2024-04-07 18:00 +0200
Re: Ain't that beautiful ? Bonita Montero <Bonita.Montero@gmail.com> - 2024-04-07 19:38 +0200
std::map advocacy Michael S <already5chosen@yahoo.com> - 2024-04-07 18:38 +0300
Re: std::map advocacy David Brown <david.brown@hesbynett.no> - 2024-04-07 18:06 +0200
Re: std::map advocacy Michael S <already5chosen@yahoo.com> - 2024-04-07 19:35 +0300
Re: std::map advocacy David Brown <david.brown@hesbynett.no> - 2024-04-08 11:29 +0200
Re: std::map advocacy Michael S <already5chosen@yahoo.com> - 2024-04-08 13:34 +0300
Re: std::map advocacy wij <wyniijj5@gmail.com> - 2024-04-08 19:18 +0800
Re: std::map advocacy Michael S <already5chosen@yahoo.com> - 2024-04-08 16:32 +0300
Re: std::map advocacy wij <wyniijj5@gmail.com> - 2024-04-09 08:40 +0800
Re: std::map advocacy Michael S <already5chosen@yahoo.com> - 2024-04-09 12:48 +0300
Re: std::map advocacy Bonita Montero <Bonita.Montero@gmail.com> - 2024-04-09 13:16 +0200
Re: std::map advocacy David Brown <david.brown@hesbynett.no> - 2024-04-08 15:30 +0200
Re: std::map advocacy scott@slp53.sl.home (Scott Lurndal) - 2024-04-08 17:19 +0000
Re: std::map advocacy Michael S <already5chosen@yahoo.com> - 2024-04-09 00:47 +0300
Re: std::map advocacy scott@slp53.sl.home (Scott Lurndal) - 2024-04-08 23:00 +0000
Re: std::map advocacy Michael S <already5chosen@yahoo.com> - 2024-04-09 02:20 +0300
Re: std::map advocacy scott@slp53.sl.home (Scott Lurndal) - 2024-04-09 15:22 +0000
Re: std::map advocacy David Brown <david.brown@hesbynett.no> - 2024-04-09 09:11 +0200
Re: std::map advocacy Michael S <already5chosen@yahoo.com> - 2024-04-09 13:12 +0300
Re: std::map advocacy David Brown <david.brown@hesbynett.no> - 2024-04-09 15:01 +0200
Re: std::map advocacy Richard Damon <richard@damon-family.org> - 2024-04-08 07:10 -0400
Re: std::map advocacy David Brown <david.brown@hesbynett.no> - 2024-04-08 15:45 +0200
Re: std::map advocacy James Kuyper <jameskuyper@alumni.caltech.edu> - 2024-04-08 19:42 -0400
Re: std::map advocacy David Brown <david.brown@hesbynett.no> - 2024-04-09 09:45 +0200
Re: std::map advocacy Michael S <already5chosen@yahoo.com> - 2024-04-09 13:27 +0300
Re: std::map advocacy David Brown <david.brown@hesbynett.no> - 2024-04-09 15:13 +0200
Re: std::map advocacy Michael S <already5chosen@yahoo.com> - 2024-04-09 18:12 +0300
Re: std::map advocacy David Brown <david.brown@hesbynett.no> - 2024-04-09 18:22 +0200
Re: std::map advocacy James Kuyper <jameskuyper@alumni.caltech.edu> - 2024-04-10 02:24 -0400
Re: std::map advocacy Michael S <already5chosen@yahoo.com> - 2024-04-11 00:07 +0300
Re: std::map advocacy Michael S <already5chosen@yahoo.com> - 2024-04-11 16:18 +0300
Re: std::map advocacy Michael S <already5chosen@yahoo.com> - 2024-04-11 16:39 +0300
Re: std::map advocacy Bonita Montero <Bonita.Montero@gmail.com> - 2024-04-11 16:21 +0200
Re: std::map advocacy Bonita Montero <Bonita.Montero@gmail.com> - 2024-04-11 15:31 +0200
Re: std::map advocacy wij <wyniijj5@gmail.com> - 2024-04-11 22:40 +0800
Re: std::map advocacy David Brown <david.brown@hesbynett.no> - 2024-04-11 16:55 +0200
Re: std::map advocacy Michael S <already5chosen@yahoo.com> - 2024-04-11 16:13 +0300
Re: std::map advocacy Paavo Helde <eesnimi@osa.pri.ee> - 2024-04-11 18:18 +0300
Re: std::map advocacy David Brown <david.brown@hesbynett.no> - 2024-04-11 09:57 +0200
Re: std::map advocacy David Brown <david.brown@hesbynett.no> - 2024-04-11 13:47 +0200
Re: std::map advocacy Bonita Montero <Bonita.Montero@gmail.com> - 2024-04-11 14:04 +0200
Re: std::map advocacy wij <wyniijj5@gmail.com> - 2024-04-11 19:25 +0800
Re: std::map advocacy scott@slp53.sl.home (Scott Lurndal) - 2024-04-07 16:09 +0000
Re: std::map advocacy Michael S <already5chosen@yahoo.com> - 2024-04-07 19:48 +0300
Re: std::map advocacy Bonita Montero <Bonita.Montero@gmail.com> - 2024-04-07 19:45 +0200
Re: std::map advocacy Paavo Helde <eesnimi@osa.pri.ee> - 2024-04-08 16:37 +0300
Re: std::map advocacy Bonita Montero <Bonita.Montero@gmail.com> - 2024-04-07 19:44 +0200
Re: std::map advocacy Michael S <already5chosen@yahoo.com> - 2024-04-08 11:15 +0300
Re: std::map advocacy Bonita Montero <Bonita.Montero@gmail.com> - 2024-04-08 14:09 +0200
Re: std::map advocacy Michael S <already5chosen@yahoo.com> - 2024-04-08 16:26 +0300
Re: std::map advocacy Bonita Montero <Bonita.Montero@gmail.com> - 2024-04-08 16:54 +0200
Re: std::map advocacy Michael S <already5chosen@yahoo.com> - 2024-04-08 20:52 +0300
Re: std::map advocacy Michael S <already5chosen@yahoo.com> - 2024-04-09 00:17 +0300
Re: std::map advocacy Bonita Montero <Bonita.Montero@gmail.com> - 2024-04-09 07:34 +0200
Re: Ain't that beautiful ? Bonita Montero <Bonita.Montero@gmail.com> - 2024-04-07 16:39 +0200
Re: Ain't that beautiful ? Michael S <already5chosen@yahoo.com> - 2024-04-07 18:41 +0300
Re: Ain't that beautiful ? Bonita Montero <Bonita.Montero@gmail.com> - 2024-04-07 19:36 +0200
Re: Ain't that beautiful ? Paavo Helde <eesnimi@osa.pri.ee> - 2024-04-07 18:25 +0300
csiph-web