Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.c++ > #118653 > unrolled thread
| Started by | Bonita Montero <Bonita.Montero@gmail.com> |
|---|---|
| First post | 2024-04-04 20:11 +0200 |
| Last post | 2024-04-07 18:25 +0300 |
| Articles | 20 on this page of 90 — 10 participants |
Back to article view | Back to comp.lang.c++
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
Page 4 of 5 — ← Prev page 1 2 3 [4] 5 Next page →
| From | James Kuyper <jameskuyper@alumni.caltech.edu> |
|---|---|
| Date | 2024-04-10 02:24 -0400 |
| Subject | Re: std::map advocacy |
| Message-ID | <uv5bbr$pndc$1@dont-email.me> |
| In reply to | #118727 |
On 4/9/24 11:12, Michael S wrote: > On Tue, 9 Apr 2024 15:13:54 +0200 > David Brown <david.brown@hesbynett.no> wrote: ... >> complexity. I only care about the implementation I am using. And I >> don't care about its average speed, I only care about its worst-case >> spaces and times. ... > You continue to argue about unimportant theoretical possibilities. He's doing the exact opposite of worrying about theorectical possibilities. He's saying that what the implementation he's using actually does is more important than your instance that it can only be doing something else.
[toc] | [prev] | [next] | [standalone]
| From | Michael S <already5chosen@yahoo.com> |
|---|---|
| Date | 2024-04-11 00:07 +0300 |
| Subject | Re: std::map advocacy |
| Message-ID | <20240411000737.000038e8@yahoo.com> |
| In reply to | #118732 |
On Wed, 10 Apr 2024 02:24:59 -0400 James Kuyper <jameskuyper@alumni.caltech.edu> wrote: > On 4/9/24 11:12, Michael S wrote: > > On Tue, 9 Apr 2024 15:13:54 +0200 > > David Brown <david.brown@hesbynett.no> wrote: > ... > >> complexity. I only care about the implementation I am using. And > >> I don't care about its average speed, I only care about its > >> worst-case spaces and times. > ... > > You continue to argue about unimportant theoretical possibilities. > > He's doing the exact opposite of worrying about theorectical > possibilities. He's saying that what the implementation he's using > actually does is more important than your instance that it can only be > doing something else. He can check and see by himself that all toolsets that he uses have std::map implemented on top of red-black tree. It's easy, sources are here. But it seems arguing is more fun. And one of the the posibilities that he mentiond (wider nodes) does not look like even theoretically possible for C++17 and later, because it would mess with extract() and the rest of node-based APIs.
[toc] | [prev] | [next] | [standalone]
| From | Michael S <already5chosen@yahoo.com> |
|---|---|
| Date | 2024-04-11 16:18 +0300 |
| Subject | Re: std::map advocacy |
| Message-ID | <20240411161800.00001239@yahoo.com> |
| In reply to | #118734 |
On Thu, 11 Apr 2024 14:04:47 +0200 Bonita Montero <Bonita.Montero@gmail.com> wrote: > Am 11.04.2024 um 13:47 schrieb David Brown: > > > Yes, most C++ users can use these standard library containers > > "blindly". And for others that have special requirements, things > > like custom allocators and other flexibilities can help. > > Custom allocators only make sense with a vector. With all other con- > tainers the standars library does a > allocator_traits<X>::rebind_alloc<Y> to have a different allocator > type. F.e. a map never uses the supplied allocator since the nodes > also contain the links. For me the whole allocator-concept mostly > doesn't make sense because of that. > I tried to implement custom allocator for std::multiset and actually succeed. But it was too hard and too ugly. So I happily forgot how to do it 2 hours later.
[toc] | [prev] | [next] | [standalone]
| From | Michael S <already5chosen@yahoo.com> |
|---|---|
| Date | 2024-04-11 16:39 +0300 |
| Subject | Re: std::map advocacy |
| Message-ID | <20240411163954.00002ba2@yahoo.com> |
| In reply to | #118736 |
On Thu, 11 Apr 2024 15:31:21 +0200 Bonita Montero <Bonita.Montero@gmail.com> wrote: > Am 11.04.2024 um 15:18 schrieb Michael S: > > On Thu, 11 Apr 2024 14:04:47 +0200 > > Bonita Montero <Bonita.Montero@gmail.com> wrote: > > > >> Am 11.04.2024 um 13:47 schrieb David Brown: > >> > >>> Yes, most C++ users can use these standard library containers > >>> "blindly". And for others that have special requirements, things > >>> like custom allocators and other flexibilities can help. > >> > >> Custom allocators only make sense with a vector. With all other > >> con- tainers the standars library does a > >> allocator_traits<X>::rebind_alloc<Y> to have a different allocator > >> type. F.e. a map never uses the supplied allocator since the nodes > >> also contain the links. For me the whole allocator-concept mostly > >> doesn't make sense because of that. > >> > > > > I tried to implement custom allocator for std::multiset and actually > > succeed. But it was too hard and too ugly. So I happily forgot how > > to do it 2 hours later. > > To make this work a custom allocator should be rebind<>-able to any > type, thereby having a typed malloc()-like allocator for all types > and sizes. > > The point is to not be more generic than absolutely necessary for particular application.
[toc] | [prev] | [next] | [standalone]
| From | Bonita Montero <Bonita.Montero@gmail.com> |
|---|---|
| Date | 2024-04-11 16:21 +0200 |
| Subject | Re: std::map advocacy |
| Message-ID | <uv8rlk$1nq5a$1@raubtier-asyl.eternal-september.org> |
| In reply to | #118737 |
Am 11.04.2024 um 15:39 schrieb Michael S: > On Thu, 11 Apr 2024 15:31:21 +0200 > Bonita Montero <Bonita.Montero@gmail.com> wrote: > >> Am 11.04.2024 um 15:18 schrieb Michael S: >>> On Thu, 11 Apr 2024 14:04:47 +0200 >>> Bonita Montero <Bonita.Montero@gmail.com> wrote: >>> >>>> Am 11.04.2024 um 13:47 schrieb David Brown: >>>> >>>>> Yes, most C++ users can use these standard library containers >>>>> "blindly". And for others that have special requirements, things >>>>> like custom allocators and other flexibilities can help. >>>> >>>> Custom allocators only make sense with a vector. With all other >>>> con- tainers the standars library does a >>>> allocator_traits<X>::rebind_alloc<Y> to have a different allocator >>>> type. F.e. a map never uses the supplied allocator since the nodes >>>> also contain the links. For me the whole allocator-concept mostly >>>> doesn't make sense because of that. >>>> >>> >>> I tried to implement custom allocator for std::multiset and actually >>> succeed. But it was too hard and too ugly. So I happily forgot how >>> to do it 2 hours later. >> >> To make this work a custom allocator should be rebind<>-able to any >> type, thereby having a typed malloc()-like allocator for all types >> and sizes. >> >> > > The point is to not be more generic than absolutely necessary for > particular application. > A rebind()-able allocator is as generic as possible. There's no way to have a pool-allocator for a container's given type since the type is always rebound.
[toc] | [prev] | [next] | [standalone]
| From | Bonita Montero <Bonita.Montero@gmail.com> |
|---|---|
| Date | 2024-04-11 15:31 +0200 |
| Subject | Re: std::map advocacy |
| Message-ID | <uv8on5$1n56q$1@raubtier-asyl.eternal-september.org> |
| In reply to | #118736 |
Am 11.04.2024 um 15:18 schrieb Michael S: > On Thu, 11 Apr 2024 14:04:47 +0200 > Bonita Montero <Bonita.Montero@gmail.com> wrote: > >> Am 11.04.2024 um 13:47 schrieb David Brown: >> >>> Yes, most C++ users can use these standard library containers >>> "blindly". And for others that have special requirements, things >>> like custom allocators and other flexibilities can help. >> >> Custom allocators only make sense with a vector. With all other con- >> tainers the standars library does a >> allocator_traits<X>::rebind_alloc<Y> to have a different allocator >> type. F.e. a map never uses the supplied allocator since the nodes >> also contain the links. For me the whole allocator-concept mostly >> doesn't make sense because of that. >> > > I tried to implement custom allocator for std::multiset and actually > succeed. But it was too hard and too ugly. So I happily forgot how to > do it 2 hours later. To make this work a custom allocator should be rebind<>-able to any type, thereby having a typed malloc()-like allocator for all types and sizes.
[toc] | [prev] | [next] | [standalone]
| From | wij <wyniijj5@gmail.com> |
|---|---|
| Date | 2024-04-11 22:40 +0800 |
| Subject | Re: std::map advocacy |
| Message-ID | <9723720a24ac8cbeb5072912a25eb1c69a7c4870.camel@gmail.com> |
| In reply to | #118734 |
On Thu, 2024-04-11 at 13:47 +0200, David Brown wrote: > On 11/04/2024 13:25, wij wrote: > > > Yup, the good point of std::list/set/map/... is that users can use it nearly > > blindingly. But when you calculate the gains/losses, things are different than > > what is usually thought. > > > Yes, most C++ users can use these standard library containers "blindly". > And for others that have special requirements, things like custom > allocators and other flexibilities can help. > > But people working on real-time systems, high-reliability systems, > safety-related systems, or very resource-constrained systems can't do > /anything/ blindly. > Understand. People here seemingly do not program hard-wares (thus don't really understand C, IMO). I quit hard-ware things (and C) for a long time. But, for embedded systems, esp. real real-time systems, my first choice was Assembly. I am not aware whether C++ is suitable for real real-time systems or not. I had encountered programming for buggy hardwares (sound efffect chips, and some badly designed hard-wares, because the company wanted to save money) where some pins had to be read/written in a peculiar way (language optimization will be a problem here). And, an embedded system that had to simulate UART where timeing is really critical in order to communicate with other devices (every machine tick counts). And a system that uses two DOS machines to work as one machine where COM1 is set to the highest priority to provide basic synchronization mechanism... And, for embedded systems, RAM/pins is money, related to survival of product. Average people don't understand this. High-level languages normally involves more supporting tools, all these need update and learning, not necessarily good.
[toc] | [prev] | [next] | [standalone]
| From | David Brown <david.brown@hesbynett.no> |
|---|---|
| Date | 2024-04-11 16:55 +0200 |
| Subject | Re: std::map advocacy |
| Message-ID | <uv8tlj$1o8cd$1@dont-email.me> |
| In reply to | #118739 |
On 11/04/2024 16:40, wij wrote: > On Thu, 2024-04-11 at 13:47 +0200, David Brown wrote: >> On 11/04/2024 13:25, wij wrote: >> >>> Yup, the good point of std::list/set/map/... is that users can use it nearly >>> blindingly. But when you calculate the gains/losses, things are different than >>> what is usually thought. >>> >> Yes, most C++ users can use these standard library containers "blindly". >> And for others that have special requirements, things like custom >> allocators and other flexibilities can help. >> >> But people working on real-time systems, high-reliability systems, >> safety-related systems, or very resource-constrained systems can't do >> /anything/ blindly. >> > > Understand. People here seemingly do not program hard-wares (thus don't really > understand C, IMO). I quit hard-ware things (and C) for a long time. But, for > embedded systems, esp. real real-time systems, my first choice was Assembly. > I am not aware whether C++ is suitable for real real-time systems or not. > C++ is fine for hard real-time and safety-critical systems - as long as you use an appropriate subset of the features, and as long as your development process is suitable. It's not any different from any other language in that respect. And I'd rate C++ above C, and C above assembly, for suitability. > I had encountered programming for buggy hardwares (sound efffect chips, and some > badly designed hard-wares, because the company wanted to save money) where > some pins had to be read/written in a peculiar way (language optimization will > be a problem here). You need to know how to access the hardware properly, and how to work with the language and the tools to achieve that. Sometimes this can be a bit fiddly, but it is entirely possible to do in a solid and reliable way. > And, an embedded system that had to simulate UART where > timeing is really critical in order to communicate with other devices (every > machine tick counts). And a system that uses two DOS machines to work as one > machine where COM1 is set to the highest priority to provide basic > synchronization mechanism... > And, for embedded systems, RAM/pins is money, related to survival of product. > Average people don't understand this. > > High-level languages normally involves more supporting tools, all these need > update and learning, not necessarily good. > Sure. (But don't update the build tools for a project - they are part of the project.)
[toc] | [prev] | [next] | [standalone]
| From | Michael S <already5chosen@yahoo.com> |
|---|---|
| Date | 2024-04-11 16:13 +0300 |
| Subject | Re: std::map advocacy |
| Message-ID | <20240411161308.00006542@yahoo.com> |
| In reply to | #118734 |
On Thu, 11 Apr 2024 19:25:44 +0800 wij <wyniijj5@gmail.com> wrote: > Yup, the good point of std::list/set/map/... is that users can use it > nearly blindingly. But when you calculate the gains/losses, things > are different than what is usually thought. > I can not see a single reason to use std::list. It brings nothing to the table relatively to my own lists and just reduces flexibility and transparency. Associative containers are very different. Even std::vector is different - while it does not bring to table a lot, it brings quite enough to prefer std over home-bred.
[toc] | [prev] | [next] | [standalone]
| From | Paavo Helde <eesnimi@osa.pri.ee> |
|---|---|
| Date | 2024-04-11 18:18 +0300 |
| Subject | Re: std::map advocacy |
| Message-ID | <uv8v0c$1ohnh$1@dont-email.me> |
| In reply to | #118740 |
11.04.2024 16:13 Michael S kirjutas: > I can not see a single reason to use std::list. It brings nothing to the > table relatively to my own lists and just reduces flexibility and > transparency. You are right, but for wrong reasons. There is usually little reason to use std::list because std::vector or std::deque is almost always a better choice. std::list might be occasionally useful for holding a bunch of entity objects whose addresses must remain unchanged.
[toc] | [prev] | [next] | [standalone]
| From | David Brown <david.brown@hesbynett.no> |
|---|---|
| Date | 2024-04-11 09:57 +0200 |
| Subject | Re: std::map advocacy |
| Message-ID | <uv854o$1j1af$1@dont-email.me> |
| In reply to | #118734 |
On 10/04/2024 23:07, Michael S wrote: > On Wed, 10 Apr 2024 02:24:59 -0400 > James Kuyper <jameskuyper@alumni.caltech.edu> wrote: > >> On 4/9/24 11:12, Michael S wrote: >>> On Tue, 9 Apr 2024 15:13:54 +0200 >>> David Brown <david.brown@hesbynett.no> wrote: >> ... >>>> complexity. I only care about the implementation I am using. And >>>> I don't care about its average speed, I only care about its >>>> worst-case spaces and times. >> ... >>> You continue to argue about unimportant theoretical possibilities. >> >> He's doing the exact opposite of worrying about theorectical >> possibilities. He's saying that what the implementation he's using >> actually does is more important than your instance that it can only be >> doing something else. > > He can check and see by himself that all toolsets that he uses have > std::map implemented on top of red-black tree. It's easy, sources are > here. But it seems arguing is more fun. No, it is /not/ easy - sources for big C++ standard libraries are far from simple to understand. (That is in no way a criticism - I understand why they are written the way they are.) I could look up sources and see identifiers or comments saying they use red-black trees, but as I have already explained several times, knowing that does not give me anywhere close to the guarantees that are needed before the code is useable for hard real-time systems. Of course I could study the code for long enough, and do enough analysis and testing to establish timing guarantees - but it would be vastly simpler and faster to write my own data structures from scratch to fulfil real-time requirements. I would not expect my implementations to be faster on average for general usage - indeed, I'd expect them to be a lot slower. But /knowing/ the limits is the important point, not the speed. If you don't know what real-time requirements are - what the phrase "real-time" means - that's fine. Most people don't need to know about it. Even most people who work with small embedded systems as a profession don't really understand it - most embedded systems don't have serious real-time requirements. But some do, and the more advanced C++ standard library features are not something that could be considered for them. If you are interesting it knowing what real-time means, I can try to explain. If you'd rather continue playing salesman for C++ standard library containers, then we'll just have to leave it. > And one of the the posibilities that he mentiond (wider nodes) does not > look like even theoretically possible for C++17 and later, because it > would mess with extract() and the rest of node-based APIs. >
[toc] | [prev] | [next] | [standalone]
| From | David Brown <david.brown@hesbynett.no> |
|---|---|
| Date | 2024-04-11 13:47 +0200 |
| Subject | Re: std::map advocacy |
| Message-ID | <uv8il4$1lr7f$1@dont-email.me> |
| In reply to | #118746 |
On 11/04/2024 13:25, wij wrote: > Yup, the good point of std::list/set/map/... is that users can use it nearly > blindingly. But when you calculate the gains/losses, things are different than > what is usually thought. > Yes, most C++ users can use these standard library containers "blindly". And for others that have special requirements, things like custom allocators and other flexibilities can help. But people working on real-time systems, high-reliability systems, safety-related systems, or very resource-constrained systems can't do /anything/ blindly.
[toc] | [prev] | [next] | [standalone]
| From | Bonita Montero <Bonita.Montero@gmail.com> |
|---|---|
| Date | 2024-04-11 14:04 +0200 |
| Subject | Re: std::map advocacy |
| Message-ID | <uv8jkr$1m2fk$1@raubtier-asyl.eternal-september.org> |
| In reply to | #118750 |
Am 11.04.2024 um 13:47 schrieb David Brown: > Yes, most C++ users can use these standard library containers "blindly". > And for others that have special requirements, things like custom > allocators and other flexibilities can help. Custom allocators only make sense with a vector. With all other con- tainers the standars library does a allocator_traits<X>::rebind_alloc<Y> to have a different allocator type. F.e. a map never uses the supplied allocator since the nodes also contain the links. For me the whole allocator-concept mostly doesn't make sense because of that.
[toc] | [prev] | [next] | [standalone]
| From | wij <wyniijj5@gmail.com> |
|---|---|
| Date | 2024-04-11 19:25 +0800 |
| Subject | Re: std::map advocacy |
| Message-ID | <9fdc553c8f60c42697bb2de21dedfc0ec8ef718b.camel@gmail.com> |
| In reply to | #118746 |
On Thu, 2024-04-11 at 09:57 +0200, David Brown wrote: > On 10/04/2024 23:07, Michael S wrote: > > On Wed, 10 Apr 2024 02:24:59 -0400 > > James Kuyper <jameskuyper@alumni.caltech.edu> wrote: > > > > > On 4/9/24 11:12, Michael S wrote: > > > > On Tue, 9 Apr 2024 15:13:54 +0200 > > > > David Brown <david.brown@hesbynett.no> wrote: > > > ... > > > > > complexity. I only care about the implementation I am using. And > > > > > I don't care about its average speed, I only care about its > > > > > worst-case spaces and times. > > > ... > > > > You continue to argue about unimportant theoretical possibilities. > > > > > > He's doing the exact opposite of worrying about theorectical > > > possibilities. He's saying that what the implementation he's using > > > actually does is more important than your instance that it can only be > > > doing something else. > > > > He can check and see by himself that all toolsets that he uses have > > std::map implemented on top of red-black tree. It's easy, sources are > > here. But it seems arguing is more fun. > > No, it is /not/ easy - sources for big C++ standard libraries are far > from simple to understand. (That is in no way a criticism - I > understand why they are written the way they are.) I could look up > sources and see identifiers or comments saying they use red-black trees, > but as I have already explained several times, knowing that does not > give me anywhere close to the guarantees that are needed before the code > is useable for hard real-time systems. Of course I could study the code > for long enough, and do enough analysis and testing to establish timing > guarantees - but it would be vastly simpler and faster to write my own > data structures from scratch to fulfil real-time requirements. I would > not expect my implementations to be faster on average for general usage > - indeed, I'd expect them to be a lot slower. But /knowing/ the limits > is the important point, not the speed. > Yup, the good point of std::list/set/map/... is that users can use it nearly blindingly. But when you calculate the gains/losses, things are different than what is usually thought. > If you don't know what real-time requirements are - what the phrase > "real-time" means - that's fine. Most people don't need to know about > it. Even most people who work with small embedded systems as a > profession don't really understand it - most embedded systems don't have > serious real-time requirements. But some do, and the more advanced C++ > standard library features are not something that could be considered for > them. > > If you are interesting it knowing what real-time means, I can try to > explain. If you'd rather continue playing salesman for C++ standard > library containers, then we'll just have to leave it. > > > And one of the the posibilities that he mentiond (wider nodes) does not > > look like even theoretically possible for C++17 and later, because it > > would mess with extract() and the rest of node-based APIs. > > > >
[toc] | [prev] | [next] | [standalone]
| From | scott@slp53.sl.home (Scott Lurndal) |
|---|---|
| Date | 2024-04-07 16:09 +0000 |
| Subject | Re: std::map advocacy |
| Message-ID | <AyzQN.166158$46Te.62838@fx38.iad> |
| In reply to | #118682 |
Michael S <already5chosen@yahoo.com> writes: >On Sun, 7 Apr 2024 16:06:02 +0200 >David Brown <david.brown@hesbynett.no> wrote: > >> >> Different people have different needs from C++, and use different >> features. If I were programming on a PC, I'd happily use std::map<> >> and the like. But I don't program on PC's, and I don't use >> std::map<>. If I needed something like that, I'd make my own class >> that fitted my requirements tightly - a factor of 10 inefficiency is >> often fine on big systems, but not on the devices I work with. >> >> But that's all fine - use whatever you find useful from the language. >> >> > >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, but >to std::map vs some form of hash, esp. when the nature of the key is >such that relatively simple hash function happens to have good >collision avoidance properties and when the database is huge, so O(1) >vs O(logN) starts to be significant. The biggest problem I have with std::map is that you cannot define a compile time map. For the application where we use map, the maps can be quite large (hundreds or thousands of entries) and initialization of those maps impacts application startup time significantly (several hundred distinct maps). We're planning on replacing std::map with a custom class optimized to efficiently handle the data (mmap'd disk file generated by a python script). A binary search on the primary key is the likely search algorithm. The maps don't change during application execution.
[toc] | [prev] | [next] | [standalone]
| From | Michael S <already5chosen@yahoo.com> |
|---|---|
| Date | 2024-04-07 19:48 +0300 |
| Subject | Re: std::map advocacy |
| Message-ID | <20240407194845.0000218c@yahoo.com> |
| In reply to | #118688 |
On Sun, 07 Apr 2024 16:09:04 GMT scott@slp53.sl.home (Scott Lurndal) wrote: > Michael S <already5chosen@yahoo.com> writes: > >On Sun, 7 Apr 2024 16:06:02 +0200 > >David Brown <david.brown@hesbynett.no> wrote: > > > >> > >> Different people have different needs from C++, and use different > >> features. If I were programming on a PC, I'd happily use > >> std::map<> and the like. But I don't program on PC's, and I don't > >> use std::map<>. If I needed something like that, I'd make my own > >> class that fitted my requirements tightly - a factor of 10 > >> inefficiency is often fine on big systems, but not on the devices > >> I work with. > >> > >> But that's all fine - use whatever you find useful from the > >> language. > >> > >> > > > >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, > >but to std::map vs some form of hash, esp. when the nature of the > >key is such that relatively simple hash function happens to have good > >collision avoidance properties and when the database is huge, so O(1) > >vs O(logN) starts to be significant. > > The biggest problem I have with std::map is that you cannot > define a compile time map. For the application where we use > map, the maps can be quite large (hundreds or thousands of entries) > and initialization of those maps impacts application startup time > significantly (several hundred distinct maps). > > We're planning on replacing std::map with a custom class optimized > to efficiently handle the data (mmap'd disk file generated by > a python script). A binary search on the primary key is the likely > search algorithm. The maps don't change during application > execution. > std::map is known to not be the best data structure for static search. Not too bad, but not the best. If you have the case where good hash function does not exist (which is extremely rare) then in your scenario simple sorted vector + binary search will likely be 1.5-2 times faster than std::map. Also when both key and payload are small, vector can be non-trivially more compact than map. Nowadays the best structures probably have to take into account cache hierarchy, so fat nodes are somewhat better than simple binary search, but that level of advancement should be used only when speed is VERY important.
[toc] | [prev] | [next] | [standalone]
| From | Bonita Montero <Bonita.Montero@gmail.com> |
|---|---|
| Date | 2024-04-07 19:45 +0200 |
| Subject | Re: std::map advocacy |
| Message-ID | <uuum49$2tk05$5@raubtier-asyl.eternal-september.org> |
| In reply to | #118690 |
Am 07.04.2024 um 18:48 schrieb Michael S: > If you have the case where good hash function does not exist (which > is extremely rare) then in your scenario simple sorted vector + binary > search will likely be 1.5-2 times faster than std::map. Also when both > key and payload are small, vector can be non-trivially more > compact than map. Use a flat_map and you'll get near to the lookup performance of a sorted vector but you'll have superior insertion or removal performance.
[toc] | [prev] | [next] | [standalone]
| From | Paavo Helde <eesnimi@osa.pri.ee> |
|---|---|
| Date | 2024-04-08 16:37 +0300 |
| Subject | Re: std::map advocacy |
| Message-ID | <uv0rul$3h7qp$1@dont-email.me> |
| In reply to | #118688 |
07.04.2024 19:09 Scott Lurndal kirjutas:
>
> The biggest problem I have with std::map is that you cannot
> define a compile time map. For the application where we use
> map, the maps can be quite large (hundreds or thousands of entries)
> and initialization of those maps impacts application startup time
> significantly (several hundred distinct maps).
>
> We're planning on replacing std::map with a custom class optimized
> to efficiently handle the data (mmap'd disk file generated by
> a python script). A binary search on the primary key is the likely
> search algorithm. The maps don't change during application execution.
If the map does not change during run, then there is no need to use any
map-like data structures or mmap files, a pre-sorted static array should
be fine for most cases. I am having multiple such "compile-time maps",
as they are not so large (tens and hundreds of entries) and do not
change often, I am maintaining them just by hand, no pre-processing
complications needed. I do not really trust my sorting abilities, so I
always also have a small function which is checking the array order (in
the Debug build, or in a unit test). A bare-bone demo:
struct A {
int x;
double y;
};
struct Entry {
std::string_view key;
A a;
};
static constexpr const Entry gLookup[] = {
{ "alpha", {1, 10.0}},
{ "beta", {2, 20.0}},
{ "gamma", {3, 30.0}}
};
#ifdef _DEBUG
// Check that I have pre-sorted my array correctly.
static struct CheckLookupTable {
CheckLookupTable() {
for (size_t i = 1; i < std::size(gLookup); ++i) {
assert(gLookup[i].key > gLookup[i - 1].key);
}
}
} gCheck;
#endif
const A* Lookup(std::string_view searchKey) {
auto it = std::lower_bound(
std::begin(gLookup),
std::end(gLookup),
searchKey,
[](const Entry& a, std::string_view b) {return a.key < b; });
return ((it != std::end(gLookup) && it->key == searchKey) ?
&(it->a):
nullptr);
}
[toc] | [prev] | [next] | [standalone]
| From | Bonita Montero <Bonita.Montero@gmail.com> |
|---|---|
| Date | 2024-04-07 19:44 +0200 |
| Subject | Re: std::map advocacy |
| Message-ID | <uuum1i$2tk05$4@raubtier-asyl.eternal-september.org> |
| In reply to | #118682 |
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 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. > 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, 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.
[toc] | [prev] | [next] | [standalone]
| From | Michael S <already5chosen@yahoo.com> |
|---|---|
| Date | 2024-04-08 11:15 +0300 |
| Subject | Re: std::map advocacy |
| Message-ID | <20240408111535.0000477e@yahoo.com> |
| In reply to | #118694 |
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.
[toc] | [prev] | [next] | [standalone]
Page 4 of 5 — ← Prev page 1 2 3 [4] 5 Next page →
Back to top | Article view | comp.lang.c++
csiph-web