Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c > #15245 > unrolled thread

[Slightly OT] Memory management and custom allocator

Back to article view | Back to comp.lang.c

Contents

  [Slightly OT] Memory management and custom allocator FtM <fmassei@gmail.com> - 2011-12-31 06:56 -0800
    Re: [Slightly OT] Memory management and custom allocator Eric Sosman <esosman@ieee-dot-org.invalid> - 2011-12-31 11:08 -0500
      Re: Memory management and custom allocator FtM <fmassei@gmail.com> - 2011-12-31 08:28 -0800
    Re: [Slightly OT] Memory management and custom allocator Johann Klammer <klammerr@NOSPAM.aon.at> - 2011-12-31 17:39 +0100
      Re: Memory management and custom allocator FtM <fmassei@gmail.com> - 2011-12-31 08:55 -0800
        Re: Memory management and custom allocator Johann Klammer <klammerr@NOSPAM.aon.at> - 2011-12-31 19:01 +0100
          Re: Memory management and custom allocator Kaz Kylheku <kaz@kylheku.com> - 2011-12-31 18:31 +0000
    Re: [Slightly OT] Memory management and custom allocator Kaz Kylheku <kaz@kylheku.com> - 2011-12-31 17:24 +0000
      Re: Memory management and custom allocator FtM <fmassei@gmail.com> - 2011-12-31 09:52 -0800
        Re: Memory management and custom allocator Eric Sosman <esosman@ieee-dot-org.invalid> - 2011-12-31 14:30 -0500
        Re: Memory management and custom allocator Markus Wichmann <nullplan@gmx.net> - 2012-01-01 12:21 +0100
          Re: Memory management and custom allocator "BartC" <bc@freeuk.com> - 2012-01-01 12:54 +0000
            Re: Memory management and custom allocator Eric Sosman <esosman@ieee-dot-org.invalid> - 2012-01-01 09:03 -0500
              Re: Memory management and custom allocator "BartC" <bc@freeuk.com> - 2012-01-01 16:23 +0000
              Re: Memory management and custom allocator jgk@panix.com (Joe keane) - 2012-01-01 21:41 +0000
                Re: Memory management and custom allocator Eric Sosman <esosman@ieee-dot-org.invalid> - 2012-01-02 08:10 -0500
                  Re: Memory management and custom allocator "BartC" <bc@freeuk.com> - 2012-01-02 14:07 +0000
                    Re: Memory management and custom allocator Eric Sosman <esosman@ieee-dot-org.invalid> - 2012-01-02 09:47 -0500
                      Re: Memory management and custom allocator FtM <fmassei@gmail.com> - 2012-01-02 08:36 -0800
                        Re: Memory management and custom allocator Eric Sosman <esosman@ieee-dot-org.invalid> - 2012-01-02 13:43 -0500
                          Re: Memory management and custom allocator FtM <fmassei@gmail.com> - 2012-01-02 11:38 -0800
                        Re: Memory management and custom allocator jgk@panix.com (Joe keane) - 2012-01-03 13:14 +0000
                          Re: Memory management and custom allocator 88888 Dihedral <dihedral88888@googlemail.com> - 2012-01-03 06:07 -0800
                            Re: Memory management and custom allocator 88888 Dihedral <dihedral88888@googlemail.com> - 2012-01-05 17:06 -0800
                      Re: Memory management and custom allocator "BartC" <bc@freeuk.com> - 2012-01-02 21:36 +0000
                        Re: Memory management and custom allocator Kaz Kylheku <kaz@kylheku.com> - 2012-01-02 21:44 +0000
                        Re: Memory management and custom allocator 88888 Dihedral <dihedral88888@googlemail.com> - 2012-01-02 23:10 -0800
                      Re: Memory management and custom allocator Keith Thompson <kst-u@mib.org> - 2012-01-02 13:42 -0800
                        Re: Memory management and custom allocator Eric Sosman <esosman@ieee-dot-org.invalid> - 2012-01-02 17:38 -0500
                  Re: Memory management and custom allocator jgk@panix.com (Joe keane) - 2012-01-02 21:45 +0000
                    Re: Memory management and custom allocator Eric Sosman <esosman@ieee-dot-org.invalid> - 2012-01-02 18:19 -0500
                      Re: Memory management and custom allocator Keith Thompson <kst-u@mib.org> - 2012-01-02 15:42 -0800
                      Re: Memory management and custom allocator "BartC" <bc@freeuk.com> - 2012-01-02 23:59 +0000
                      Re: Memory management and custom allocator Kleuske <kleuske@nowhere.net> - 2012-01-03 11:38 +0000
                        Re: Memory management and custom allocator "BartC" <bc@freeuk.com> - 2012-01-03 12:49 +0000
                      Re: Memory management and custom allocator jgk@panix.com (Joe keane) - 2012-01-04 23:42 +0000
                        Re: Memory management and custom allocator Eric Sosman <esosman@ieee-dot-org.invalid> - 2012-01-04 20:23 -0500
                        Re: Memory management and custom allocator Phil Carmody <thefatphil_demunged@yahoo.co.uk> - 2012-01-05 23:31 +0200
                  Re: Memory management and custom allocator jgk@panix.com (Joe keane) - 2012-01-04 21:52 +0000
                    Re: Memory management and custom allocator Eric Sosman <esosman@ieee-dot-org.invalid> - 2012-01-04 20:31 -0500
                      Re: Memory management and custom allocator "BartC" <bc@freeuk.com> - 2012-01-05 01:45 +0000
                        Re: Memory management and custom allocator Phil Carmody <thefatphil_demunged@yahoo.co.uk> - 2012-01-07 05:55 +0200
                          Re: Memory management and custom allocator "BartC" <bc@freeuk.com> - 2012-01-07 12:02 +0000
            Re: Memory management and custom allocator Eric Sosman <esosman@ieee-dot-org.invalid> - 2012-01-01 09:08 -0500
              Re: Memory management and custom allocator FtM <fmassei@gmail.com> - 2012-01-01 10:08 -0800
                Re: Memory management and custom allocator "BartC" <bc@freeuk.com> - 2012-01-01 23:34 +0000
                  Re: Memory management and custom allocator FtM <fmassei@gmail.com> - 2012-01-02 02:18 -0800
                    Re: Memory management and custom allocator 88888 Dihedral <dihedral88888@googlemail.com> - 2012-01-02 02:34 -0800
                      Re: Memory management and custom allocator FtM <fmassei@gmail.com> - 2012-01-02 02:43 -0800
                        Re: Memory management and custom allocator 88888 Dihedral <dihedral88888@googlemail.com> - 2012-01-02 03:11 -0800
                          Re: Memory management and custom allocator FtM <fmassei@gmail.com> - 2012-01-02 08:17 -0800
                    Re: Memory management and custom allocator "BartC" <bc@freeuk.com> - 2012-01-02 11:40 +0000
                      Re: Memory management and custom allocator FtM <fmassei@gmail.com> - 2012-01-02 08:27 -0800
            Re: Memory management and custom allocator "BartC" <bc@freeuk.com> - 2012-01-01 23:26 +0000
              Re: Memory management and custom allocator Ben Bacarisse <ben.usenet@bsb.me.uk> - 2012-01-01 23:54 +0000
                Re: Memory management and custom allocator "BartC" <bc@freeuk.com> - 2012-01-02 00:32 +0000
            Re: Memory management and custom allocator Kaz Kylheku <kaz@kylheku.com> - 2012-01-02 02:46 +0000
              Re: Memory management and custom allocator "BartC" <bc@freeuk.com> - 2012-01-02 11:53 +0000
                Re: Memory management and custom allocator Ben Bacarisse <ben.usenet@bsb.me.uk> - 2012-01-02 15:18 +0000
            Re: Memory management and custom allocator jgk@panix.com (Joe keane) - 2012-01-03 12:21 +0000
            Re: Memory management and custom allocator Karl Malbrain <malbrain@yahoo.com> - 2012-01-04 16:48 -0800
              Re: Memory management and custom allocator "BartC" <bc@freeuk.com> - 2012-01-05 01:36 +0000
    Re: [Slightly OT] Memory management and custom allocator "io_x" <a@b.c.invalid> - 2012-01-01 17:02 +0100
    Re: [Slightly OT] Memory management and custom allocator jgk@panix.com (Joe keane) - 2012-01-01 21:21 +0000
    Re: [Slightly OT] Memory management and custom allocator 88888 Dihedral <dihedral88888@googlemail.com> - 2012-01-01 21:01 -0800
    Re: [Slightly OT] Memory management and custom allocator 88888 Dihedral <dihedral88888@googlemail.com> - 2012-01-07 05:20 -0800

Page 2 of 4 — ← Prev page 1 [2] 3 4  Next page →

#15333 — Re: Memory management and custom allocator

On Jan 2, 7:43 pm, Eric Sosman <esos...@ieee-dot-org.invalid> wrote:
> On 1/2/2012 11:36 AM, FtM wrote:
>
> > [...]
> > Someone previously asked me what if the allocation took no cycles at
> > all. That question is obviously plain wrong, [...]
>
>      Part of the problem is that you have not made your objectives
> clear.  Kaz apparently believed you were seeking an allocator that
> would consume less CPU to perform its job -- indeed, that's exactly
> how I understand some of your remarks.  In that context his question
> is not "plain wrong" at all, but entirely to the point: He's asking
> about the upper bound on potential improvement.  If you could reduce
> the allocator's time to zero -- if you could achieve an infinite
> speedup -- how much overall improvement would you attain?  If you
> cannot answer that question, at least with a well-grounded estimate,
> you have *no* business trying to speed up the allocator, nor the sort,
> nor the parser, nor the hash table, nor the frammis rebiculator.
>
>      If you have not measured, you do not know whether you are in
> trouble.  If you achieve an X% improvement, you *still* won't know
> whether you are out of trouble or still in it.
>

Yup, reading again what I wrote from this point of view I understand
his question. I was a little bit harsh because on the one hand in my
opinion the "speed" was only a part of the problem, and on the other
hand I know that I can't measure anything before implementing
something that I think its a good idea..

> > [...] I *do* like the
> > allocator taking cycles if this means that, when the memory is low, my
> > complex data structure resides in one single page and the system has
> > not to hysterically swap from disk to deal with a pathological
> > fragmentation.
>
>      A memory manager with C's semantics, that is, one that cannot
> relocate an already-allocated block, is *always* vulnerable to
> fragmentation (J.M. Robson, JACM 18, 416-423).  The practical issue
> is to find strategies that "usually" don't suffer from "severe"
> fragmentation in "typical" cases.
>

That's very interesting, I didn't know that it was mathematically
proved! Anyway.. [read below]

> > With your comment anyway you are agreeing with me: what if you could
> > choose? :-)
>
>      Sorry; I don't understand this remark.
>

... if for your own use you give up the standard interface and
manually choose which allocation strategy best fit your needs, you
could have an advantage.

A very practical example. Someone use my library just for the linked-
lists, implemented with this hypothetical allocator. His code uses the
allocator of its choice, probably the system's one, and of course he
will have one or more linked-lists accessed from time to time; these
lists will hardly suffer severe fragmentation (if any), no matter how
or when he inserts or deletes their elements, simply because the
memory was already allocated from the start.
If all of this can be useful or not depends on the specific library
user's needs, but personally I think that giving this possibility
would be a nice-to-have feature.

Ciao!

[toc] | [prev] | [next] | [standalone]

#15371 — Re: Memory management and custom allocator

In article <f500e5bf-edc1-43f7-9fbe-cf7bac512531@t16g2000vba.googlegroups.com>,
FtM  <fmassei@gmail.com> wrote:
>That question is obviously plain wrong, because I *do* like the
>allocator taking cycles if this means that, when the memory is low, my
>complex data structure resides in one single page and the system has
>not to hysterically swap from disk to deal with a pathological
>fragmentation.

IMHE, people who try to make the allocation 'as fast as possible' are
just chasing a squirrel up the wrong tree.

No sir, you want to make your clients' code as fast as possible.

Sometimes people recommend a class-based linked list ('look!  it's two
instructions!').  In my onion, this is disasterous.  Works great for toy
programs, but when you have lots-of-data and long-running combined, your
memory turns into an omelet.

You may as well send invitations to Mr. Cache Miss and Ms. Tlb Fail...

If you have a 'fast' allocator that doesn't have the slighest idea of
locality, and a 'slow' allocator that takes some care of it, the
'slower' code will kick the 'faster' code arse every time.

[toc] | [prev] | [next] | [standalone]

#15372 — Re: Memory management and custom allocator

Joe keane於 2012年1月3日星期二UTC+8下午9時14分46秒寫道：
> In article <f500e5bf-edc1-43f7...@t16g2000vba.googlegroups.com>,
> FtM  <fma...@gmail.com> wrote:
> >That question is obviously plain wrong, because I *do* like the
> >allocator taking cycles if this means that, when the memory is low, my
> >complex data structure resides in one single page and the system has
> >not to hysterically swap from disk to deal with a pathological
> >fragmentation.
> 
> IMHE, people who try to make the allocation 'as fast as possible' are
> just chasing a squirrel up the wrong tree.
> 
> No sir, you want to make your clients' code as fast as possible.
> 
> Sometimes people recommend a class-based linked list ('look!  it's two
> instructions!').  In my onion, this is disasterous.  Works great for toy
> programs, but when you have lots-of-data and long-running combined, your
> memory turns into an omelet.
> 
> You may as well send invitations to Mr. Cache Miss and Ms. Tlb Fail...
> 
> If you have a 'fast' allocator that doesn't have the slighest idea of
> locality, and a 'slow' allocator that takes some care of it, the
> 'slower' code will kick the 'faster' code arse every time.

This is a system level problem. The allocator under a huge dram  space with 
a lot free space remained should be designed toward fast easily. 

But if the dram is near fully allocated then a good heap walker that can 
swap pages to the hard disk is important toward reliability not the speed 
part in the allocator to degrade the system speed. 
 


  

[toc] | [prev] | [next] | [standalone]

#15480 — Re: Memory management and custom allocator

88888 Dihedral於 2012年1月3日星期二UTC+8下午10時07分20秒寫道：
> Joe keane於 2012年1月3日星期二UTC+8下午9時14分46秒寫道：
> > In article <f500e5bf-e...@t16g2000vba.googlegroups.com>,
> > FtM  <fma...@gmail.com> wrote:
> > >That question is obviously plain wrong, because I *do* like the
> > >allocator taking cycles if this means that, when the memory is low, my
> > >complex data structure resides in one single page and the system has
> > >not to hysterically swap from disk to deal with a pathological
> > >fragmentation.
> > 
> > IMHE, people who try to make the allocation 'as fast as possible' are
> > just chasing a squirrel up the wrong tree.
> > 
> > No sir, you want to make your clients' code as fast as possible.
> > 
> > Sometimes people recommend a class-based linked list ('look!  it's two
> > instructions!').  In my onion, this is disasterous.  Works great for toy
> > programs, but when you have lots-of-data and long-running combined, your
> > memory turns into an omelet.
> > 
> > You may as well send invitations to Mr. Cache Miss and Ms. Tlb Fail...
> > 
> > If you have a 'fast' allocator that doesn't have the slighest idea of
> > locality, and a 'slow' allocator that takes some care of it, the
> > 'slower' code will kick the 'faster' code arse every time.
> 
> This is a system level problem. The allocator under a huge dram  space with 
> a lot free space remained should be designed toward fast easily. 
> 
> But if the dram is near fully allocated then a good heap walker that can 
> swap pages to the hard disk is important toward reliability not the speed 
> part in the allocator to degrade the system speed.

The heap managing module is very important in the OS. 

Normally all allocations from malloc are allocated in sizes of 2's powers
that are 2 to S powers for S=4, 5, 6, ..12 to 16. 

A page might be 2K bytes or 64K or even 4M(20 bits) bytes in various systems.

There are trivial details. 

The heap walker part for each node in the heap space is more important. 

After a heap walk, the buddy algorithm can be applied. 

Do we need to discuss the details here?

  

 

[toc] | [prev] | [next] | [standalone]

#15338 — Re: Memory management and custom allocator

"Eric Sosman" <esosman@ieee-dot-org.invalid> wrote in message
news:jdsg2h$mkb$1@dont-email.me...
> On 1/2/2012 9:07 AM, BartC wrote:

>> Such structs are easier to index in arrays.
>
>     Nonsense.  The `[]' operator works with equal ease on arrays
> of any element size at all.

Where an address calculation is needed, then it's usually multiply versus a
shift. Although turning 44 bytes/element into 64 just for that reason would
not be worth it. There should be other benefits to using 64.

> As for straddling VM pages, denser packing wins over bloated "nicer"
> packing any day.  Consider again the example of a thousand structs: I
> want to use 44KB, you're suggesting 64KB would be "nicer."  Suppose an
> 8KB page: You want to use eight pages, I want to use six.  Suppose a
> 64B cache line: You want to use a thousand cache lines, I want to use
> six hundred eighty-eight.

You forgot the bit where I suggested trying to get it down to 32 bytes. So
some data structures could get smaller.

You would only expand one up to the next power-of-two if there was a net
benefit. Keeping 20 bytes unused out of 64 wouldn't be a benefit. Storing
something in there that would have needed it's own space anyway might well
be.

(While most structs you'd leave alone because there aren't going to be
enough of them, or accessed often enough, to worry about.)

>> You can't design a struct to be 8- or
>> 12-bytes smaller than a power-of-two; every system will be different.
>
>     You can't design it to be exactly 64 bytes, either.  Quick: How
> many bytes in a `long double'?  What's the alignment requirement of
> a function pointer?  What is the "unit" size of a bit-field?

I'm pretty good at that actually..

(I've just been looking at an old application of mine. There is one struct
that has an 8-byte padding field added at the end to bring the size up to
exactly 128 bytes. Would that really have made a difference or not? Let's
see!

Running the application with a struct size of 128 bytes, the runtime was 48
seconds (this is for a 3D hidden line display). I took out the padding
field, and the runtime wentup to 59 seconds, 23% slower. Now that could be 
due to a million reasons, but all the same, I think I'll leave that padding 
in, thanks!)

-- 
Bartc 

[toc] | [prev] | [next] | [standalone]

#15341 — Re: Memory management and custom allocator

On 2012-01-02, BartC <bc@freeuk.com> wrote:
> "Eric Sosman" <esosman@ieee-dot-org.invalid> wrote in message
> news:jdsg2h$mkb$1@dont-email.me...
>> On 1/2/2012 9:07 AM, BartC wrote:
>
>>> Such structs are easier to index in arrays.
>>
>>     Nonsense.  The `[]' operator works with equal ease on arrays
>> of any element size at all.
>
> Where an address calculation is needed, then it's usually multiply versus a
> shift. Although turning 44 bytes/element into 64 just for that reason would
> not be worth it. There should be other benefits to using 64.

Note that 44 is 32 + 8 + 4, and so 44x  is (32x + 8x + 4x). Your CPU can
multiply by 44 just by doing three shifts and two additions, which can likely
be parallelized.

[toc] | [prev] | [next] | [standalone]

#15357 — Re: Memory management and custom allocator

Bart於 2012年1月3日星期二UTC+8上午5時36分45秒寫道：
> "Eric Sosman" <esosman@ieee-dot-org.invalid> wrote in message
> news:jdsg2h$mkb$1@dont-email.me...
> > On 1/2/2012 9:07 AM, BartC wrote:
> 
> >> Such structs are easier to index in arrays.
> >
> >     Nonsense.  The `[]' operator works with equal ease on arrays
> > of any element size at all.
> 
> Where an address calculation is needed, then it's usually multiply versus a
> shift. Although turning 44 bytes/element into 64 just for that reason would
> not be worth it. There should be other benefits to using 64.
> 
> > As for straddling VM pages, denser packing wins over bloated "nicer"
> > packing any day.  Consider again the example of a thousand structs: I
> > want to use 44KB, you're suggesting 64KB would be "nicer."  Suppose an
> > 8KB page: You want to use eight pages, I want to use six.  Suppose a
> > 64B cache line: You want to use a thousand cache lines, I want to use
> > six hundred eighty-eight.
> 
> You forgot the bit where I suggested trying to get it down to 32 bytes. So
> some data structures could get smaller.
> 
> You would only expand one up to the next power-of-two if there was a net
> benefit. Keeping 20 bytes unused out of 64 wouldn't be a benefit. Storing
> something in there that would have needed it's own space anyway might well
> be.
> 

This is OK. I remembered that I did my own heap manager for digital
videos or images long time ago. Every instance is of millions of true 
color pixels and can be magnified to 16 times in one dimension to be viewed. 

It is not difficult at all but just a little bit tedious. 
 
 


> (While most structs you'd leave alone because there aren't going to be
> enough of them, or accessed often enough, to worry about.)
> 
> >> You can't design a struct to be 8- or
> >> 12-bytes smaller than a power-of-two; every system will be different.
> >
> >     You can't design it to be exactly 64 bytes, either.  Quick: How
> > many bytes in a `long double'?  What's the alignment requirement of
> > a function pointer?  What is the "unit" size of a bit-field?
> 
> I'm pretty good at that actually..
> 
> (I've just been looking at an old application of mine. There is one struct
> that has an 8-byte padding field added at the end to bring the size up to
> exactly 128 bytes. Would that really have made a difference or not? Let's
> see!
> 
> Running the application with a struct size of 128 bytes, the runtime was 48
> seconds (this is for a 3D hidden line display). I took out the padding
> field, and the runtime wentup to 59 seconds, 23% slower. Now that could be 
> due to a million reasons, but all the same, I think I'll leave that padding 
> in, thanks!)
> 
> -- 
> Bartc

[toc] | [prev] | [next] | [standalone]

#15339 — Re: Memory management and custom allocator

Eric Sosman <esosman@ieee-dot-org.invalid> writes:
[...]
>> This is where you redesign your struct to use only 32 bytes, or find a
>> good use for another 20 bytes to make 64.
[...]
>> Such structs are easier to index in arrays.
>
>      Nonsense.  The `[]' operator works with equal ease on arrays
> of any element size at all.
[...]

It's certainly possible that `[]' on an array of 64-bytes elements
will be faster than `[]' on an array with 44-byte elements.
(It's also possible that it could have the same or even slower
performance.)

But padding a structure to make it 64 bytes for the purpose of making
array indexing faster is a classic case of micro-optimization, to
be attempted only if measurements show that it makes a significant
difference.

-- 
Keith Thompson (The_Other_Keith) kst-u@mib.org  <http://www.ghoti.net/~kst>
    Will write code for food.
"We must do something.  This is something.  Therefore, we must do this."
    -- Antony Jay and Jonathan Lynn, "Yes Minister"

[toc] | [prev] | [next] | [standalone]

#15345 — Re: Memory management and custom allocator

On 1/2/2012 4:42 PM, Keith Thompson wrote:
> Eric Sosman<esosman@ieee-dot-org.invalid>  writes:
> [...]
>>> This is where you redesign your struct to use only 32 bytes, or find a
>>> good use for another 20 bytes to make 64.
> [...]
>>> Such structs are easier to index in arrays.
>>
>>       Nonsense.  The `[]' operator works with equal ease on arrays
>> of any element size at all.
> [...]
>
> It's certainly possible that `[]' on an array of 64-bytes elements
> will be faster than `[]' on an array with 44-byte elements.
> (It's also possible that it could have the same or even slower
> performance.)

     Note that he didn't claim "faster" or "slower," but "easier."
The claim is, I repeat, nonsense.

> But padding a structure to make it 64 bytes for the purpose of making
> array indexing faster is a classic case of micro-optimization, to
> be attempted only if measurements show that it makes a significant
> difference.

     It's probably not even micro-optimization; I'll stick with my
hypothesis that it's numerological superstition.

     The original remark was

	[...] if you're being sensible and trying to keep to
	power-of-two allocations [...]

... and I'm objecting to the implication that power-of-two sizes are
in any way "sensible" for their own sake.  That's just bogus.

-- 
Eric Sosman
esosman@ieee-dot-org.invalid

[toc] | [prev] | [next] | [standalone]

#15342 — Re: Memory management and custom allocator

In article <jdsact$nr6$1@dont-email.me>,
Eric Sosman  <esosman@ieee-dot-org.invalid> wrote:
>     If you have a forty-four-byte struct and allocate sixty-four
>bytes to hold it, how have you avoided *either* sort of "waste?"

I think the context is where you're writing some dynamic array
[e.g. string or vector] and you have some control over the sequence of
capacities [at least that's what i thought].  Of course, you do not want
to call realloc on every operation; you want the progression to be
exponential.  In such a case, powers of two are very logical.

[toc] | [prev] | [next] | [standalone]

#15347 — Re: Memory management and custom allocator

On 1/2/2012 4:45 PM, Joe keane wrote:
> In article<jdsact$nr6$1@dont-email.me>,
> Eric Sosman<esosman@ieee-dot-org.invalid>  wrote:
>>      If you have a forty-four-byte struct and allocate sixty-four
>> bytes to hold it, how have you avoided *either* sort of "waste?"
>
> I think the context is where you're writing some dynamic array
> [e.g. string or vector] and you have some control over the sequence of
> capacities [at least that's what i thought].  Of course, you do not want
> to call realloc on every operation; you want the progression to be
> exponential.  In such a case, powers of two are very logical.

     (Shrug.)  No more logical than powers of three, or of three halves
(`size += size/2').

     I don't know when the number Two starts to exercise its mystical
fascination for programmers, but the fascination certainly exists: You
find people reaching for powers of two "just because," with no actual
reason for the choice.  Maybe it's when the neophyte first learns that
he can sometimes shift instead of multiplying and dividing, or that he
can use AND to calculate some remainders.  This may strike the young
and credulous as evidence that Two is magical, and just as some folks
never get over the Tooth Fairy, others never get over the Two'th Fairy.

     Yes, folks, yes, there certainly *are* circumstances where power-
of-two sizes are Just What The Doctor Ordered.  But there's no good
reason to make everything in sight a power of two!  If you allocate
128 array elements to represent the 88 keys of a piano, or sixteen
for the Twelve Days of Christmas, or thirty-two for your fingers and
toes, you're just being silly.  Or superstitious.

-- 
Eric Sosman
esosman@ieee-dot-org.invalid

[toc] | [prev] | [next] | [standalone]

#15348 — Re: Memory management and custom allocator

Eric Sosman <esosman@ieee-dot-org.invalid> writes:
[...]
>      Yes, folks, yes, there certainly *are* circumstances where power-
> of-two sizes are Just What The Doctor Ordered.  But there's no good
> reason to make everything in sight a power of two!  If you allocate
> 128 array elements to represent the 88 keys of a piano, or sixteen
> for the Twelve Days of Christmas, or thirty-two for your fingers and
> toes, you're just being silly.  Or superstitious.

Or polydactyl.

-- 
Keith Thompson (The_Other_Keith) kst-u@mib.org  <http://www.ghoti.net/~kst>
    Will write code for food.
"We must do something.  This is something.  Therefore, we must do this."
    -- Antony Jay and Jonathan Lynn, "Yes Minister"

[toc] | [prev] | [next] | [standalone]

#15349 — Re: Memory management and custom allocator

"Eric Sosman" <esosman@ieee-dot-org.invalid> wrote in message 
news:jdte21$im7$1@dont-email.me...

>     Yes, folks, yes, there certainly *are* circumstances where power-
> of-two sizes are Just What The Doctor Ordered.  But there's no good
> reason to make everything in sight a power of two!  If you allocate
> 128 array elements to represent the 88 keys of a piano, or sixteen
> for the Twelve Days of Christmas, or thirty-two for your fingers and
> toes, you're just being silly.  Or superstitious.

Odd how the C standard seems preoccupied with such numbers then (or with 
powers-of-two-minus-one, the same thing):

(from 5.2.4.1:)

"- 127 nesting levels of blocks
- 63 nesting levels of conditional inclusion
- 12 pointer, array, and function declarators (in any combinations)
- 63 nesting levels of parenthesized declarators within a full declarator
- 63 nesting levels of parenthesized expressions within a full expression
- 63 significant initial characters in an internal identifier or a macro
- 31 significant initial characters in an external identifier
- 4095 external identifiers in one translation unit
- 511 identifiers with block scope declared in one block
- 4095 macro identifiers simultaneously defined in one
- 127 parameters in one function definition
- 127 arguments in one function call
- 127 parameters in one macro definition
- 127 arguments in one macro invocation
- 4095 characters in a logical source line
- 4095 characters in a character string literal or wide string literal
- 65535 bytes in an object (in a hosted environment only)
- 15 nesting levels for #included files
- 1023 case labels for a switch statement
- 1023 members in a single structure or union
- 1023 enumeration constants in a single enumeration
- 63 levels of nested structure"

(But I'm not sure how that 12 got in there, on the third line; a typo?)

-- 
Bartc 

[toc] | [prev] | [next] | [standalone]

#15360 — Re: Memory management and custom allocator

On Mon, 02 Jan 2012 18:19:29 -0500, Eric Sosman saw fit to publish the
following:
<snip>

>      Yes, folks, yes, there certainly *are* circumstances where power-
> of-two sizes are Just What The Doctor Ordered.  But there's no good
> reason to make everything in sight a power of two!  If you allocate 128
> array elements to represent the 88 keys of a piano, or sixteen for the
> Twelve Days of Christmas, or thirty-two for your fingers and toes,
> you're just being silly.  Or superstitious.

Bravo! I couldn't have put it better than that.

-- 
Spock: The odds of surviving another attack are 13562190123 to 1, Captain.

[toc] | [prev] | [next] | [standalone]

#15367 — Re: Memory management and custom allocator

"Kleuske" <kleuske@nowhere.net> wrote in message
news:jdupbb$om0$3@dont-email.me...
> On Mon, 02 Jan 2012 18:19:29 -0500, Eric Sosman saw fit to publish the
> following:
> <snip>
>
>>      Yes, folks, yes, there certainly *are* circumstances where power-
>> of-two sizes are Just What The Doctor Ordered.  But there's no good
>> reason to make everything in sight a power of two!  If you allocate 128
>> array elements to represent the 88 keys of a piano, or sixteen for the
>> Twelve Days of Christmas, or thirty-two for your fingers and toes,
>> you're just being silly.  Or superstitious.
>
> Bravo! I couldn't have put it better than that.

For user applications, I also agree with all this; there shouldn't be all
these mysterious powers-of-two floating around for no good reason. (And if
you've ever been involved in writing user manuals, the less to have to
explain, the better.)

For higher level, rapid development languages, they are also largely
irrelevant.

But C is a somewhat lower level language, and these powers of two do get
everywhere. You can completely ignore them if you wish, but if often pays to
be aware of them.

Anything that can only be described, or indexed, in N bits, will have 2^N
possibilities; you can't away from that. (And hardware seems to prefer N
itself as a power-of-two; so 8 bits in a byte is more common than 5, 7 or
11.)

And part of the context of this thread is memory allocation strategies, 
where there might well be merit in a scheme were allocated blocks can only 
change in size by a power of two (and which, if implemented too thinly on 
top of malloc(), is affected by malloc()'s own overheads).

I don't think that is being obsessed with it.

-- 
Bartc 

[toc] | [prev] | [next] | [standalone]

#15426 — Re: Memory management and custom allocator

In article <jdte21$im7$1@dont-email.me>,
Eric Sosman  <esosman@ieee-dot-org.invalid> wrote:
>     I don't know when the number Two starts to exercise its mystical
>fascination for programmers, but the fascination certainly exists: You
>find people reaching for powers of two "just because," with no actual
>reason for the choice.

You have 'struct x', you add padding, test it, it is faster.  You have
'struct y', you add padding, test it, it is faster.  You have 'struct
z', you add padding, test it, it is faster.  You have 'struct w', you
add padding, test it, it is slower [oops doesn't always work].

You have 'struct a', and your boss says 'can't test!  just guess!'.
What would you do?

[toc] | [prev] | [next] | [standalone]

#15436 — Re: Memory management and custom allocator

On 1/4/2012 6:42 PM, Joe keane wrote:
> In article<jdte21$im7$1@dont-email.me>,
> Eric Sosman<esosman@ieee-dot-org.invalid>  wrote:
>>      I don't know when the number Two starts to exercise its mystical
>> fascination for programmers, but the fascination certainly exists: You
>> find people reaching for powers of two "just because," with no actual
>> reason for the choice.
>
> You have 'struct x', you add padding, test it, it is faster.  You have
> 'struct y', you add padding, test it, it is faster.  You have 'struct
> z', you add padding, test it, it is faster.  You have 'struct w', you
> add padding, test it, it is slower [oops doesn't always work].
>
> You have 'struct a', and your boss says 'can't test!  just guess!'.
> What would you do?

     I'd leave it alone, because there are more important things
to attend to.

-- 
Eric Sosman
esosman@ieee-dot-org.invalid

[toc] | [prev] | [next] | [standalone]

#15474 — Re: Memory management and custom allocator

jgk@panix.com (Joe keane) writes:
> In article <jdte21$im7$1@dont-email.me>,
> Eric Sosman  <esosman@ieee-dot-org.invalid> wrote:
> >     I don't know when the number Two starts to exercise its mystical
> >fascination for programmers, but the fascination certainly exists: You
> >find people reaching for powers of two "just because," with no actual
> >reason for the choice.
> 
> You have 'struct x', you add padding, test it, it is faster.  You have
> 'struct y', you add padding, test it, it is faster.  You have 'struct
> z', you add padding, test it, it is faster.  You have 'struct w', you
> add padding, test it, it is slower [oops doesn't always work].
> 
> You have 'struct a', and your boss says 'can't test!  just guess!'.
> What would you do?

I'd ask my boss if he's heard of Knuth.

However, it's hypothetical, I'd probably not be working at such a 
company in the first place.

Phil
-- 
Unix is simple. It just takes a genius to understand its simplicity
-- Dennis Ritchie (1941-2011), Unix Co-Creator

[toc] | [prev] | [next] | [standalone]

#15416 — Re: Memory management and custom allocator

In article <jdsact$nr6$1@dont-email.me>,
Eric Sosman  <esosman@ieee-dot-org.invalid> wrote:
>     If you have a forty-four-byte struct and allocate sixty-four
>bytes to hold it, how have you avoided *either* sort of "waste?"

If the cache line is 16 bytes, we know that each object will take only
three lines; the fourth is never used [it may be worse with the VM].
For this case 48 would work just as well (the compiler will do that for
you if it thinks 8-byte alignment is a good idea).  But then if the
cache line is 32 bytes, same argument applies.

[toc] | [prev] | [next] | [standalone]

#15439 — Re: Memory management and custom allocator

On 1/4/2012 4:52 PM, Joe keane wrote:
> In article<jdsact$nr6$1@dont-email.me>,
> Eric Sosman<esosman@ieee-dot-org.invalid>  wrote:
>>      If you have a forty-four-byte struct and allocate sixty-four
>> bytes to hold it, how have you avoided *either* sort of "waste?"
>
> If the cache line is 16 bytes, we know that each object will take only
> three lines; the fourth is never used [it may be worse with the VM].
> For this case 48 would work just as well (the compiler will do that for
> you if it thinks 8-byte alignment is a good idea).  But then if the
> cache line is 32 bytes, same argument applies.

     All I can say is that you and I have divergent notions of
efficiency.  I'm thinking "I can run over the entire array with
just N*44/C cache misses; Joe would prefer N*64/C."  That is, I
think you'll incur 46% more cache misses than I will.  Tell me
again, please, what I have wasted by using 31% fewer cache line
loads than you would?

     I'm also thinking "I need N*44/P pages for my array; Joe would
rather use N*64/P."  That is, I think your working set size will
be 46% larger than mine, your likelihood of taking a page fault
will be 46% greater than mine.  Tell me again, please, what have
I wasted by using 31% fewer memory pages?

     It's an odd sort of "waste" that spends fewer resources.

-- 
Eric Sosman
esosman@ieee-dot-org.invalid

[toc] | [prev] | [next] | [standalone]

Page 2 of 4 — ← Prev page 1 [2] 3 4  Next page →

Back to top | Article view | comp.lang.c

csiph-web