Groups > comp.lang.c++ > #19106

Re: C/C++ question about dynamic "static struct"

From	Juha Nieminen <nospam@thanks.invalid>
Newsgroups	comp.lang.c++, comp.lang.c
Subject	Re: C/C++ question about dynamic "static struct"
Date	2012-10-19 21:22 +0000
Organization	Aioe.org NNTP Server
Message-ID	<k5sgah$md2$1@speranza.aioe.org> (permalink)
References	(5 earlier) <8q66l9-lkm.ln1@wilbur.25thandClement.com> <k5r6da$at5$1@speranza.aioe.org> <k5recc$f0i$1@dont-email.me> <k5ri2t$87d$1@speranza.aioe.org> <XnsA0F1E8F23D9ACmyfirstnameosapriee@216.196.109.131>

Cross-posted to 2 groups.

Show all headers | View raw

In comp.lang.c++ Paavo Helde <myfirstname@osa.pri.ee> wrote:
> Now I'm curious. Is there any fundamental reason why "C/C++ standard 
> allocator tends to have horrendous efficiency" (leaving aside the 
> compacting bit)? I'm sure people have put a lot of wisdom and work into 
> standard allocators, why would my custom allocator on top of the standard 
> one behave better?

According to my tests, the two major reasons for the slowness are
cache inefficiency and thread-safety.

Especially in situations where little random-sized blocks of memory
are constantly being allocated and deallocated pretty at random (at
least from the allocator's point of view, which obviously doesn't see
any logic, just the allocation requests), the memory gets more and
more fragmented, and the list of free blocks gets more and more
randomized. This means that after a little while most memory blocks
will be located at wildly random locations, causing lots of cache misses
(both when allocated and deallocated, and also when accesses from the
program).

This is where memory compaction could help a lot. Even if the compaction
takes some resources, the end result is that after the process subsequent
allocations will be enormously faster (because they are much more cache
friendly.) The overall speed of the program could see significant increases
(depending a lot on the program, of course.)

Cache optimality is not something to be dismissed lightly. Even inside
your own code you can achieve enormous speedups by organizing the
memory usage such that it becomes more cache-efficient (by increasing
cache locality.) A program can become several times faster just because
of this.

The other reason is that the C standard allocator (also used by C++) is
thread-safe: It's ready as-is to be used in multithreaded programs. This
inevitably causes overhead (which would be unneeded especially in a
single-threaded program.)

While according to my experiments it has got a lot better (perhaps
because of development, or because of better hardware, or possibly
a combination of both), it still causes a quite measurable slowdown.

I don't know exactly how a JVM memory allocator solves both problems,
but seemingly they tend to be pretty good at it (helped by the fact
that Java's semantics allows for things like memory compaction.)

Thread

C/C++ question about dynamic "static struct" gus gassmann <gus@nospam.com> - 2012-10-17 06:49 -0300
  Re: C/C++ question about dynamic "static struct" Noob <root@127.0.0.1> - 2012-10-17 13:08 +0200
    Re: C/C++ question about dynamic "static struct" James Kuyper <jameskuyper@verizon.net> - 2012-10-17 08:19 -0400
    Re: C/C++ question about dynamic "static struct" Jorgen Grahn <grahn+nntp@snipabacken.se> - 2012-10-17 15:19 +0000
    Re: C/C++ question about dynamic "static struct" gus gassmann <gus@nospam.com> - 2012-10-17 18:47 -0300
      Re: C/C++ question about dynamic "static struct" Ike Naar <ike@iceland.freeshell.org> - 2012-10-17 22:46 +0000
        Re: C/C++ question about dynamic "static struct" Juha Nieminen <nospam@thanks.invalid> - 2012-10-18 07:13 +0000
      Re: C/C++ question about dynamic "static struct" James Kuyper <jameskuyper@verizon.net> - 2012-10-17 18:58 -0400
        Re: C/C++ question about dynamic "static struct" Stuart <DerTopper@web.de> - 2012-10-18 09:55 +0200
          Re: C/C++ question about dynamic "static struct" jacob navia <jacob@spamsink.net> - 2012-10-18 10:13 +0200
            Re: C/C++ question about dynamic "static struct" Juha Nieminen <nospam@thanks.invalid> - 2012-10-18 08:23 +0000
              Re: C/C++ question about dynamic "static struct" jacob navia <jacob@spamsink.net> - 2012-10-18 11:17 +0200
                Re: C/C++ question about dynamic "static struct" Ian Collins <ian-news@hotmail.com> - 2012-10-18 23:37 +1300
                Re: C/C++ question about dynamic "static struct" Rui Maciel <rui.maciel@gmail.com> - 2012-10-18 15:35 +0100
                Re: C/C++ question about dynamic "static struct" Öö Tiib <ootiib@hot.ee> - 2012-10-19 11:40 -0700
            Re: C/C++ question about dynamic "static struct" Ian Collins <ian-news@hotmail.com> - 2012-10-18 21:45 +1300
            Re: C/C++ question about dynamic "static struct" Rui Maciel <rui.maciel@gmail.com> - 2012-10-18 15:03 +0100
          Re: C/C++ question about dynamic "static struct" James Kuyper <jameskuyper@verizon.net> - 2012-10-18 07:18 -0400
            Re: C/C++ question about dynamic "static struct" Stuart <DerTopper@web.de> - 2012-10-18 17:43 +0200
          Re: C/C++ question about dynamic "static struct" William Ahern <william@wilbur.25thandClement.com> - 2012-10-18 13:52 -0700
            Re: C/C++ question about dynamic "static struct" Ian Collins <ian-news@hotmail.com> - 2012-10-19 21:34 +1300
            Re: C/C++ question about dynamic "static struct" Stuart <DerTopper@web.de> - 2012-10-19 11:03 +0200
              Re: C/C++ question about dynamic "static struct" "BartC" <bc@freeuk.com> - 2012-10-20 14:03 +0100
            Re: C/C++ question about dynamic "static struct" Juha Nieminen <nospam@thanks.invalid> - 2012-10-19 09:27 +0000
              Re: C/C++ question about dynamic "static struct" Stuart <DerTopper@web.de> - 2012-10-19 13:43 +0200
                Re: C/C++ question about dynamic "static struct" Juha Nieminen <nospam@thanks.invalid> - 2012-10-19 12:46 +0000
                Re: C/C++ question about dynamic "static struct" ImpalerCore <jadill33@gmail.com> - 2012-10-19 10:14 -0700
                Re: C/C++ question about dynamic "static struct" Paavo Helde <myfirstname@osa.pri.ee> - 2012-10-19 14:53 -0500
                Re: C/C++ question about dynamic "static struct" Öö Tiib <ootiib@hot.ee> - 2012-10-19 13:52 -0700
                Re: C/C++ question about dynamic "static struct" Öö Tiib <ootiib@hot.ee> - 2012-10-19 14:13 -0700
                Re: C/C++ question about dynamic "static struct" Juha Nieminen <nospam@thanks.invalid> - 2012-10-19 21:24 +0000
                Re: C/C++ question about dynamic "static struct" Ian Collins <ian-news@hotmail.com> - 2012-10-20 11:47 +1300
                Re: C/C++ question about dynamic "static struct" Juha Nieminen <nospam@thanks.invalid> - 2012-10-19 21:22 +0000
              Re: C/C++ question about dynamic "static struct" William Ahern <william@wilbur.25thandClement.com> - 2012-10-19 11:21 -0700
                Re: C/C++ question about dynamic "static struct" Juha Nieminen <nospam@thanks.invalid> - 2012-10-19 21:29 +0000
                Re: C/C++ question about dynamic "static struct" James Kuyper <jameskuyper@verizon.net> - 2012-10-19 18:53 -0400
                Re: C/C++ question about dynamic "static struct" Ian Collins <ian-news@hotmail.com> - 2012-10-20 12:13 +1300
                Re: C/C++ question about dynamic "static struct" Juha Nieminen <nospam@thanks.invalid> - 2012-10-20 05:55 +0000
                Re: C/C++ question about dynamic "static struct" Stuart <DerTopper@web.de> - 2012-10-20 13:24 +0200
                Re: C/C++ question about dynamic "static struct" Ben Bacarisse <ben.usenet@bsb.me.uk> - 2012-10-20 12:54 +0100
                Re: C/C++ question about dynamic "static struct" Nick Keighley <nick_keighley_nospam@hotmail.com> - 2012-10-20 06:45 -0700
                Re: C/C++ question about dynamic "static struct" Ian Collins <ian-news@hotmail.com> - 2012-10-21 09:20 +1300
                Re: C/C++ question about dynamic "static struct" Dombo <dombo@disposable.invalid> - 2012-10-20 22:28 +0200
                Re: C/C++ question about dynamic "static struct" Juha Nieminen <nospam@thanks.invalid> - 2012-10-21 07:05 +0000
                Re: C/C++ question about dynamic "static struct" Les Cargill <lcargill99@comcast.com> - 2012-10-21 02:23 -0500
                Re: C/C++ question about dynamic "static struct" Juha Nieminen <nospam@thanks.invalid> - 2012-10-21 07:32 +0000
                Re: C/C++ question about dynamic "static struct" "BartC" <bc@freeuk.com> - 2012-10-21 11:56 +0100
                Re: C/C++ question about dynamic "static struct" Les Cargill <lcargill99@comcast.com> - 2012-10-21 12:54 -0500
                Re: C/C++ question about dynamic "static struct" ptyxs <kerloch@gmail.com> - 2012-10-22 13:43 +0200
                Re: C/C++ question about dynamic "static struct" gwowen <gwowen@gmail.com> - 2012-10-26 03:37 -0700
                Re: C/C++ question about dynamic "static struct" Les Cargill <lcargill99@comcast.com> - 2012-10-26 07:33 -0500
                Re: C/C++ question about dynamic "static struct" Nick Keighley <nick_keighley_nospam@hotmail.com> - 2012-10-27 05:14 -0700
                Re: C/C++ question about dynamic "static struct" Nick Keighley <nick_keighley_nospam@hotmail.com> - 2012-10-27 05:08 -0700
                Re: C/C++ question about dynamic "static struct" Les Cargill <lcargill99@comcast.com> - 2012-10-20 13:44 -0500
                Re: C/C++ question about dynamic "static struct" Ian Collins <ian-news@hotmail.com> - 2012-10-21 09:09 +1300
                Re: C/C++ question about dynamic "static struct" Dombo <dombo@disposable.invalid> - 2012-10-20 22:31 +0200
                Re: C/C++ question about dynamic "static struct" Les Cargill <lcargill99@comcast.com> - 2012-10-21 02:11 -0500
                Re: C/C++ question about dynamic "static struct" Ian Collins <ian-news@hotmail.com> - 2012-10-21 20:28 +1300
                Re: C/C++ question about dynamic "static struct" Juha Nieminen <nospam@thanks.invalid> - 2012-10-21 07:40 +0000
                Re: C/C++ question about dynamic "static struct" Les Cargill <lcargill99@comcast.com> - 2012-10-21 13:31 -0500
                Re: C/C++ question about dynamic "static struct" Ian Collins <ian-news@hotmail.com> - 2012-10-22 08:41 +1300
                Re: C/C++ question about dynamic "static struct" Les Cargill <lcargill99@comcast.com> - 2012-10-21 16:24 -0500
                Re: C/C++ question about dynamic "static struct" Öö Tiib <ootiib@hot.ee> - 2012-10-21 15:05 -0700
                Re: C/C++ question about dynamic "static struct" Juha Nieminen <nospam@thanks.invalid> - 2012-10-22 07:52 +0000
                Re: C/C++ question about dynamic "static struct" Les Cargill <lcargill99@comcast.com> - 2012-10-22 14:02 -0500
                Re: C/C++ question about dynamic "static struct" gwowen <gwowen@gmail.com> - 2012-10-26 03:41 -0700
                Re: C/C++ question about dynamic "static struct" Les Cargill <lcargill99@comcast.com> - 2012-10-26 07:53 -0500
                Re: C/C++ question about dynamic "static struct" James Kuyper <jameskuyper@verizon.net> - 2012-10-26 09:51 -0400
                Re: C/C++ question about dynamic "static struct" James Kuyper <jameskuyper@verizon.net> - 2012-10-26 13:48 -0400
                Re: C/C++ question about dynamic "static struct" ImpalerCore <jadill33@gmail.com> - 2012-10-26 07:35 -0700
                Re: C/C++ question about dynamic "static struct" Paavo Helde <myfirstname@osa.pri.ee> - 2012-10-26 18:42 -0500
                Re: C/C++ question about dynamic "static struct" ImpalerCore <jadill33@gmail.com> - 2012-10-27 04:21 -0700
                Re: C/C++ question about dynamic "static struct" Öö Tiib <ootiib@hot.ee> - 2012-10-27 05:04 -0700
                Re: C/C++ question about dynamic "static struct" Paavo Helde <myfirstname@osa.pri.ee> - 2012-10-27 08:06 -0500
                Re: C/C++ question about dynamic "static struct" ImpalerCore <jadill33@gmail.com> - 2012-10-27 06:50 -0700
                Re: C/C++ question about dynamic "static struct" Paavo Helde <myfirstname@osa.pri.ee> - 2012-10-27 11:13 -0500
                Re: C/C++ question about dynamic "static struct" ImpalerCore <jadill33@gmail.com> - 2012-10-27 12:02 -0700
                Re: C/C++ question about dynamic "static struct" Paavo Helde <myfirstname@osa.pri.ee> - 2012-10-27 15:46 -0500
                Re: C/C++ question about dynamic "static struct" ImpalerCore <jadill33@gmail.com> - 2012-10-27 20:24 -0700
                Re: C/C++ question about dynamic "static struct" Dombo <dombo@disposable.invalid> - 2012-10-27 20:11 +0200
                Re: C/C++ question about dynamic "static struct" Nick Keighley <nick_keighley_nospam@hotmail.com> - 2012-10-27 05:43 -0700
                Re: C/C++ question about dynamic "static struct" Les Cargill <lcargill99@comcast.com> - 2012-10-27 13:52 -0500
                Re: C/C++ question about dynamic "static struct" Les Cargill <lcargill99@comcast.com> - 2012-10-27 14:40 -0500
                Re: C/C++ question about dynamic "static struct" google@ianshome.com - 2012-10-23 12:03 -0700
                Re: C/C++ question about dynamic "static struct" Nick Keighley <nick_keighley_nospam@hotmail.com> - 2012-10-27 05:35 -0700
                Re: C/C++ question about dynamic "static struct" Les Cargill <lcargill99@comcast.com> - 2012-10-27 14:24 -0500
                Re: C/C++ question about dynamic "static struct" Nick Keighley <nick_keighley_nospam@hotmail.com> - 2012-10-27 05:36 -0700
                Re: C/C++ question about dynamic "static struct" Juha Nieminen <nospam@thanks.invalid> - 2012-10-21 07:08 +0000
                Re: C/C++ question about dynamic "static struct" Les Cargill <lcargill99@comcast.com> - 2012-10-21 02:51 -0500
                Re: C/C++ question about dynamic "static struct" Ian Collins <ian-news@hotmail.com> - 2012-10-21 21:09 +1300
                Re: C/C++ question about dynamic "static struct" Rui Maciel <rui.maciel@gmail.com> - 2012-10-21 12:16 +0100
                Re: C/C++ question about dynamic "static struct" Rui Maciel <rui.maciel@gmail.com> - 2012-10-21 11:55 +0100
                Re: C/C++ question about dynamic "static struct" Les Cargill <lcargill99@comcast.com> - 2012-10-21 13:47 -0500
                Re: C/C++ question about dynamic "static struct" Ian Collins <ian-news@hotmail.com> - 2012-10-22 08:46 +1300
                Re: C/C++ question about dynamic "static struct" Rui Maciel <rui.maciel@gmail.com> - 2012-10-22 03:02 +0100
                Re: C/C++ question about dynamic "static struct" Juha Nieminen <nospam@thanks.invalid> - 2012-10-22 08:04 +0000
                Re: C/C++ question about dynamic "static struct" Tobias Müller <troplin@bluewin.ch> - 2012-10-21 18:54 +0000
                Re: C/C++ question about dynamic "static struct" Ian Collins <ian-news@hotmail.com> - 2012-10-22 08:49 +1300
                Re: C/C++ question about dynamic "static struct" Tobias Müller <troplin@bluewin.ch> - 2012-10-21 20:07 +0000
                Re: C/C++ question about dynamic "static struct" Öö Tiib <ootiib@hot.ee> - 2012-10-21 13:53 -0700
                Re: C/C++ question about dynamic "static struct" Ian Collins <ian-news@hotmail.com> - 2012-10-22 09:54 +1300
                Re: C/C++ question about dynamic "static struct" Rui Maciel <rui.maciel@gmail.com> - 2012-10-22 02:41 +0100
                Re: C/C++ question about dynamic "static struct" Tobias Müller <troplin@bluewin.ch> - 2012-10-22 06:12 +0000
                Re: C/C++ question about dynamic "static struct" Jorgen Grahn <grahn+nntp@snipabacken.se> - 2012-10-22 20:52 +0000
                Re: C/C++ question about dynamic "static struct" Öö Tiib <ootiib@hot.ee> - 2012-10-22 16:30 -0700
                Re: C/C++ question about dynamic "static struct" Stuart <DerTopper@web.de> - 2012-10-23 11:22 +0200
                Re: C/C++ question about dynamic "static struct" Jorgen Grahn <grahn+nntp@snipabacken.se> - 2012-10-23 16:58 +0000
                Re: C/C++ question about dynamic "static struct" Rui Maciel <rui.maciel@gmail.com> - 2012-10-22 02:22 +0100
                Re: C/C++ question about dynamic "static struct" Nick Keighley <nick_keighley_nospam@hotmail.com> - 2012-10-27 05:30 -0700
                Re: C/C++ question about dynamic "static struct" James Kuyper <jameskuyper@verizon.net> - 2012-10-20 09:06 -0400
                Re: C/C++ question about dynamic "static struct" Öö Tiib <ootiib@hot.ee> - 2012-10-20 07:43 -0700
                Re: C/C++ question about dynamic "static struct" Juha Nieminen <nospam@thanks.invalid> - 2012-10-21 07:11 +0000
                Re: C/C++ question about dynamic "static struct" Rui Maciel <rui.maciel@gmail.com> - 2012-10-21 11:56 +0100
                Re: C/C++ question about dynamic "static struct" James Kuyper <jameskuyper@verizon.net> - 2012-10-21 07:43 -0400
                Re: C/C++ question about dynamic "static struct" Öö Tiib <ootiib@hot.ee> - 2012-10-21 10:36 -0700
                Re: C/C++ question about dynamic "static struct" Juha Nieminen <nospam@thanks.invalid> - 2012-10-22 08:13 +0000
                Re: C/C++ question about dynamic "static struct" Steve Thompson <stevet810@gmail.com> - 2012-10-22 15:08 +0000
                Re: C/C++ question about dynamic "static struct" James Kuyper <jameskuyper@verizon.net> - 2012-10-22 14:42 -0400
                Re: C/C++ question about dynamic "static struct" Rui Maciel <rui.maciel@gmail.com> - 2012-10-21 10:12 +0100
                Re: C/C++ question about dynamic "static struct" Les Cargill <lcargill99@comcast.com> - 2012-10-20 13:24 -0500
                Re: C/C++ question about dynamic "static struct" Juha Nieminen <nospam@thanks.invalid> - 2012-10-21 07:16 +0000
                Re: C/C++ question about dynamic "static struct" Les Cargill <lcargill99@comcast.com> - 2012-10-21 13:57 -0500
                Re: C/C++ question about dynamic "static struct" Juha Nieminen <nospam@thanks.invalid> - 2012-10-22 08:17 +0000
              Re: C/C++ question about dynamic "static struct" Fritz Wuehler <fritz@spamexpire-201210.rodent.frell.theremailer.net> - 2012-10-20 22:41 +0200
                Re: C/C++ question about dynamic "static struct" Dombo <dombo@disposable.invalid> - 2012-10-21 01:04 +0200
                Re: C/C++ question about dynamic "static struct" Juha Nieminen <nospam@thanks.invalid> - 2012-10-21 07:23 +0000
            Re: C/C++ question about dynamic "static struct" Jorgen Grahn <grahn+nntp@snipabacken.se> - 2012-10-21 19:33 +0000
              Re: C/C++ question about dynamic "static struct" Greg Martin <greg@softsprocket.com> - 2012-10-21 13:20 -0700
                Re: C/C++ question about dynamic "static struct" Jorgen Grahn <grahn+nntp@snipabacken.se> - 2012-10-23 15:44 +0000
                Re: C/C++ question about dynamic "static struct" Dombo <dombo@disposable.invalid> - 2012-10-23 20:01 +0200
                Re: C/C++ question about dynamic "static struct" Stuart <DerTopper@web.de> - 2012-10-24 12:01 +0200
                Re: C/C++ question about dynamic "static struct" Dombo <dombo@disposable.invalid> - 2012-10-24 20:31 +0200
          Re: C/C++ question about dynamic "static struct" Nick Keighley <nick_keighley_nospam@hotmail.com> - 2012-10-20 06:13 -0700
            Re: C/C++ question about dynamic "static struct" Juha Nieminen <nospam@thanks.invalid> - 2012-10-21 07:25 +0000
              Re: C/C++ question about dynamic "static struct" Nick Keighley <nick_keighley_nospam@hotmail.com> - 2012-10-27 05:54 -0700
          Re: C/C++ question about dynamic "static struct" Old Wolf <oldwolf@inspire.net.nz> - 2012-11-11 14:58 -0800
            Re: C/C++ question about dynamic "static struct" gof@somewhere.invalid (Adam Wysocki) - 2012-11-12 10:33 +0000
      Re: C/C++ question about dynamic "static struct" Ian Collins <ian-news@hotmail.com> - 2012-10-18 12:19 +1300
    Re: C/C++ question about dynamic "static struct" Juha Nieminen <nospam@thanks.invalid> - 2012-10-18 07:06 +0000
      Re: C/C++ question about dynamic "static struct" Noob <root@127.0.0.1> - 2012-10-18 11:36 +0200
        Re: C/C++ question about dynamic "static struct" Juha Nieminen <nospam@thanks.invalid> - 2012-10-19 09:28 +0000
          Re: C/C++ question about dynamic "static struct" Noob <root@127.0.0.1> - 2012-10-19 12:07 +0200
            Re: C/C++ question about dynamic "static struct" gus gassmann <gus@nospam.com> - 2012-10-19 08:03 -0300
              Re: C/C++ question about dynamic "static struct" Fritz Wuehler <fritz@spamexpire-201210.rodent.frell.theremailer.net> - 2012-10-20 07:14 +0200
          Re: C/C++ question about dynamic "static struct" James Kuyper <jameskuyper@verizon.net> - 2012-10-19 06:58 -0400
  Re: C/C++ question about dynamic "static struct" James Kuyper <jameskuyper@verizon.net> - 2012-10-17 08:29 -0400
  Re: C/C++ question about dynamic "static struct" Richard Damon <news.x.richarddamon@xoxy.net> - 2012-10-17 08:35 -0400
    Re: C/C++ question about dynamic "static struct" James Kuyper <jameskuyper@verizon.net> - 2012-10-17 08:49 -0400
    Re: C/C++ question about dynamic "static struct" Juha Nieminen <nospam@thanks.invalid> - 2012-10-18 07:10 +0000
      Re: C/C++ question about dynamic "static struct" Keith Thompson <kst-u@mib.org> - 2012-10-18 12:11 -0700
        Re: C/C++ question about dynamic "static struct" Juha Nieminen <nospam@thanks.invalid> - 2012-10-19 09:30 +0000
          Re: C/C++ question about dynamic "static struct" Keith Thompson <kst-u@mib.org> - 2012-10-19 03:05 -0700
          Re: C/C++ question about dynamic "static struct" James Kuyper <jameskuyper@verizon.net> - 2012-10-19 07:37 -0400

csiph-web