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

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

Malloc Query

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

Contents

  Malloc Query Pushpa <pushpa@nospam.invalid> - 2011-05-17 19:39 +0000
    Re: Malloc Query blp@cs.stanford.edu (Ben Pfaff) - 2011-05-17 12:55 -0700
      Re: Malloc Query "BartC" <bc@freeuk.com> - 2011-05-18 12:05 +0100
        Re: Malloc Query Pushpa <pushpa@nospam.invalid> - 2011-05-18 17:11 +0000
          Re: Malloc Query "BartC" <bc@freeuk.com> - 2011-05-18 22:42 +0100
          Re: Malloc Query Eric Sosman <esosman@ieee-dot-org.invalid> - 2011-05-18 21:10 -0400
        Re: Malloc Query Ben Bacarisse <ben.usenet@bsb.me.uk> - 2011-05-18 19:34 +0100
          Re: Malloc Query Uncle Steve <stevet810@gmail.com> - 2011-05-18 17:10 -0400
            Re: Malloc Query Ben Bacarisse <ben.usenet@bsb.me.uk> - 2011-05-19 00:26 +0100
              Re: Malloc Query Uncle Steve <stevet810@gmail.com> - 2011-05-18 21:25 -0400
                Re: Malloc Query James Kuyper <jameskuyper@verizon.net> - 2011-05-18 21:38 -0400
                  Re: Malloc Query Uncle Steve <stevet810@gmail.com> - 2011-05-19 14:11 -0400
                    Re: Malloc Query James Kuyper <jameskuyper@verizon.net> - 2011-05-19 22:55 -0400
                      Re: Malloc Query Uncle Steve <stevet810@gmail.com> - 2011-05-20 12:14 -0400
                Re: Malloc Query Ben Bacarisse <ben.usenet@bsb.me.uk> - 2011-05-19 03:22 +0100
                  Re: Malloc Query Uncle Steve <stevet810@gmail.com> - 2011-05-19 14:20 -0400
                    Re: Malloc Query Ben Bacarisse <ben.usenet@bsb.me.uk> - 2011-05-19 23:51 +0100
                      Re: Malloc Query Uncle Steve <stevet810@gmail.com> - 2011-05-19 20:01 -0400
                    Re: Malloc Query luser- -droog <mijoryx@yahoo.com> - 2011-05-22 02:49 -0700
                      Re: Malloc Query Uncle Steve <stevet810@gmail.com> - 2011-05-22 10:46 -0400
                        Re: Malloc Query Shao Miller <sha0.miller@gmail.com> - 2011-05-22 12:37 -0500
                          Re: Malloc Query Shao Miller <sha0.miller@gmail.com> - 2011-05-22 13:02 -0500
                          Re: Malloc Query Uncle Steve <stevet810@gmail.com> - 2011-05-22 14:12 -0400
                            Re: Malloc Query Shao Miller <sha0.miller@gmail.com> - 2011-05-23 03:06 -0500
                              Re: Malloc Query luser- -droog <mijoryx@yahoo.com> - 2011-05-23 00:42 -0700
                              Re: Malloc Query Uncle Steve <stevet810@gmail.com> - 2011-05-23 11:10 -0400
                                Re: Malloc Query Keith Thompson <kst-u@mib.org> - 2011-05-23 09:06 -0700
                        Re: Malloc Query Ben Bacarisse <ben.usenet@bsb.me.uk> - 2011-05-22 23:18 +0100
                          Re: Malloc Query Uncle Steve <stevet810@gmail.com> - 2011-05-22 19:18 -0400
                            Re: Malloc Query Ian Collins <ian-news@hotmail.com> - 2011-05-23 11:22 +1200
                              Re: Malloc Query Uncle Steve <stevet810@gmail.com> - 2011-05-23 01:57 -0400
                                Re: Malloc Query Ian Collins <ian-news@hotmail.com> - 2011-05-23 19:24 +1200
                                  Re: Malloc Query Uncle Steve <stevet810@gmail.com> - 2011-05-23 14:20 -0400
                                    Re: Malloc Query Ian Collins <ian-news@hotmail.com> - 2011-05-24 07:41 +1200
                                      Re: Malloc Query Uncle Steve <stevet810@gmail.com> - 2011-05-23 16:24 -0400
                                        Re: Malloc Query Ian Collins <ian-news@hotmail.com> - 2011-05-24 09:20 +1200
                                          Re: Malloc Query Uncle Steve <stevet810@gmail.com> - 2011-05-23 18:05 -0400
                                            Re: Malloc Query Ian Collins <ian-news@hotmail.com> - 2011-05-24 10:37 +1200
                                              Re: Malloc Query Uncle Steve <stevet810@gmail.com> - 2011-05-23 19:34 -0400
                                      Re: Malloc Query "robertwessel2@yahoo.com" <robertwessel2@yahoo.com> - 2011-05-23 17:48 -0700
                                        Re: Malloc Query Ian Collins <ian-news@hotmail.com> - 2011-05-24 12:56 +1200
                                    Re: Malloc Query James Kuyper <jameskuyper@verizon.net> - 2011-05-24 07:19 -0400
                                      Re: Malloc Query Uncle Steve <stevet810@gmail.com> - 2011-05-24 11:32 -0400
                            Re: Malloc Query Ben Bacarisse <ben.usenet@bsb.me.uk> - 2011-05-23 01:04 +0100
                              Re: Malloc Query Uncle Steve <stevet810@gmail.com> - 2011-05-23 02:36 -0400
                                Re: Malloc Query luser- -droog <mijoryx@yahoo.com> - 2011-05-23 00:39 -0700
                                Re: Malloc Query Ben Bacarisse <ben.usenet@bsb.me.uk> - 2011-05-23 14:44 +0100
                                  Re: Malloc Query Seebs <usenet-nospam@seebs.net> - 2011-05-23 15:16 +0000
                                  Re: Malloc Query Uncle Steve <stevet810@gmail.com> - 2011-05-23 11:41 -0400
                                  Re: Malloc Query David Thompson <dave.thompson2@verizon.net> - 2011-06-01 16:33 -0400
                  Re: Malloc Query Uncle Steve <stevet810@gmail.com> - 2011-05-19 18:34 -0400
                    Re: Malloc Query Ben Bacarisse <ben.usenet@bsb.me.uk> - 2011-05-20 02:36 +0100
                      Re: Malloc Query Uncle Steve <stevet810@gmail.com> - 2011-05-20 12:26 -0400
                        Re: Malloc Query Ben Bacarisse <ben.usenet@bsb.me.uk> - 2011-05-20 23:32 +0100
                          Re: Malloc Query Uncle Steve <stevet810@gmail.com> - 2011-05-20 21:17 -0400
                    Re: Malloc Query Ian Collins <ian-news@hotmail.com> - 2011-05-21 14:30 +1200
                      Re: Malloc Query Uncle Steve <stevet810@gmail.com> - 2011-05-21 11:13 -0400
                        Re: Malloc Query Ian Collins <ian-news@hotmail.com> - 2011-05-22 08:50 +1200
                          Re: Malloc Query Uncle Steve <stevet810@gmail.com> - 2011-05-21 20:03 -0400
                            Re: Malloc Query Ian Collins <ian-news@hotmail.com> - 2011-05-22 13:23 +1200
                              Re: Malloc Query Uncle Steve <stevet810@gmail.com> - 2011-05-22 10:01 -0400
                    Re: Malloc Query "io_x" <a@b.c.invalid> - 2011-05-26 08:12 +0200
                      Re: Malloc Query Ian Collins <ian-news@hotmail.com> - 2011-05-26 19:16 +1200
                        Re: Malloc Query Uncle Steve <stevet810@gmail.com> - 2011-05-26 15:03 -0400
                          Re: Malloc Query Ian Collins <ian-news@hotmail.com> - 2011-05-27 09:16 +1200
                            Re: Malloc Query Uncle Steve <stevet810@gmail.com> - 2011-05-26 17:55 -0400
                          Re: Malloc Query "io_x" <a@b.c.invalid> - 2011-05-27 05:47 +0200
                      Re: Malloc Query Uncle Steve <stevet810@gmail.com> - 2011-05-26 15:02 -0400
          Re: Malloc Query "BartC" <bc@freeuk.com> - 2011-05-18 22:31 +0100
            Re: Malloc Query Ben Bacarisse <ben.usenet@bsb.me.uk> - 2011-05-18 23:37 +0100
              Re: Malloc Query "BartC" <bc@freeuk.com> - 2011-05-19 01:50 +0100
                Re: Malloc Query Ben Bacarisse <ben.usenet@bsb.me.uk> - 2011-05-19 02:50 +0100
                  Re: Malloc Query "BartC" <bc@freeuk.com> - 2011-05-19 12:14 +0100
                    Re: Malloc Query Ben Bacarisse <ben.usenet@bsb.me.uk> - 2011-05-19 15:10 +0100
                      Re: Malloc Query "BartC" <bc@freeuk.com> - 2011-05-19 15:48 +0100
        Re: Malloc Query cri@tiac.net (Richard Harter) - 2011-05-18 19:31 +0000
        Re: Malloc Query Ike Naar <ike@iceland.freeshell.org> - 2011-05-18 21:43 +0000
          Re: Malloc Query "BartC" <bc@freeuk.com> - 2011-05-18 22:58 +0100
    Re: Malloc Query Joe Pfeiffer <pfeiffer@cs.nmsu.edu> - 2011-05-17 14:01 -0600
    Re: Malloc Query Columbus sailed the ocean China Blue <chine.bleu@yahoo.com> - 2011-05-17 13:21 -0700
    Re: Malloc Query BGB <cr88192@hotmail.com> - 2011-05-17 14:08 -0700
      Re: Malloc Query Michael Press <rubrum@pacbell.net> - 2011-05-17 19:49 -0700
    Re: Malloc Query Lauri Alanko <la@iki.fi> - 2011-05-18 00:50 +0000
    Re: Malloc Query Eric Sosman <esosman@ieee-dot-org.invalid> - 2011-05-17 21:21 -0400
      Re: Malloc Query "io_x" <a@b.c.invalid> - 2011-05-18 19:31 +0200
      Re: Malloc Query Jorgen Grahn <grahn+nntp@snipabacken.se> - 2011-05-18 21:36 +0000
        Re: Malloc Query Eric Sosman <esosman@ieee-dot-org.invalid> - 2011-05-18 21:26 -0400
      Re: Malloc Query Tim Rentsch <txr@alumni.caltech.edu> - 2011-05-19 02:07 -0700
        Re: Malloc Query Ian Collins <ian-news@hotmail.com> - 2011-05-19 21:13 +1200
    Re: Malloc Query Nobody <nobody@nowhere.com> - 2011-05-18 07:08 +0100
    Re: Malloc Query David Resnick <lndresnick@gmail.com> - 2011-05-19 07:51 -0700
      Re: Malloc Query Joe Pfeiffer <pfeiffer@cs.nmsu.edu> - 2011-05-19 09:12 -0600

Page 1 of 5  [1] 2 3 4 5  Next page →

#4178 — Malloc Query

Hi all,

Many users claim that malloc() and free() provided by the language
library results in considerable
amount of overhead in terms of calling the same. Can we really
eliminate overhead by using
used defined functions/user defined memory manager. Is there any
significant advantage in providing user defined malloc() and free(). I
want to exclude realtime systems or embedded systems which are memory
constrained here.
I am talking about general purpose applications. With a user defined
memory manager can it handle
memory allocation and de-allocation in a much better way than what OS
would have done. Any inputs/comments
on the same are highly appreciated.

Thanks and Regards,
Pushpa

[toc] | [next] | [standalone]

#4180

Pushpa <pushpa@nospam.invalid> writes:

> Many users claim that malloc() and free() provided by the language
> library results in considerable
> amount of overhead in terms of calling the same. Can we really
> eliminate overhead by using
> used defined functions/user defined memory manager. Is there any
> significant advantage in providing user defined malloc() and
> free().

According to an academic study I read some time ago, there is
rarely any significant advantage to special-purpose memory
allocators.  In a quick online search, I didn't find a reference
to this paper, but perhaps someone else here has a copy of it.
-- 
"It wouldn't be a new C standard if it didn't give a
 new meaning to the word `static'."
--Peter Seebach on C99

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

#4220

"Ben Pfaff" <blp@cs.stanford.edu> wrote in message 
news:87aael3xw1.fsf@blp.benpfaff.org...
> Pushpa <pushpa@nospam.invalid> writes:
>
>> Many users claim that malloc() and free() provided by the language
>> library results in considerable
>> amount of overhead in terms of calling the same. Can we really
>> eliminate overhead by using
>> used defined functions/user defined memory manager. Is there any
>> significant advantage in providing user defined malloc() and
>> free().
>
> According to an academic study I read some time ago, there is
> rarely any significant advantage to special-purpose memory
> allocators.  In a quick online search, I didn't find a reference
> to this paper, but perhaps someone else here has a copy of it.

I've just done a test where allocating and freeing large numbers of 4-byte 
blocks took twenty times longer using malloc/free (and probably took 2-4 
times as much space) than using a special allocator.

How significant this is depends on the application, but I don't think you 
can just dismiss such an allocator.

-- 
Bartc 

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

#4230

BartC writes:
> "Ben Pfaff" <blp@cs.stanford.edu> wrote in message
> news:87aael3xw1.fsf@blp.benpfaff.org...
>> Pushpa <pushpa@nospam.invalid> writes:
>>
>>> Many users claim that malloc() and free() provided by the language
>>> library results in considerable
>>> amount of overhead in terms of calling the same. Can we really
>>> eliminate overhead by using
>>> used defined functions/user defined memory manager. Is there any
>>> significant advantage in providing user defined malloc() and free().
>>
>> According to an academic study I read some time ago, there is rarely
>> any significant advantage to special-purpose memory allocators.  In a
>> quick online search, I didn't find a reference to this paper, but
>> perhaps someone else here has a copy of it.
> 
> I've just done a test where allocating and freeing large numbers of
> 4-byte blocks took twenty times longer using malloc/free (and probably
> took 2-4 times as much space) than using a special allocator.
> 
> How significant this is depends on the application, but I don't think
> you can just dismiss such an allocator.

Bartc: Are you sure of this? What I really wanted to ask: Is it 
reasonable to plan for saving 50% of memory allocation time by rewriting 
special functions for same ? If speedup can be 20X this is amazing.

Kind Regards
Pushpa

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

#4249

"Pushpa" <pushpa@nospam.invalid> wrote in message
news:ir0ukr$iu8$1@speranza.aioe.org...
> BartC writes:

>> I've just done a test where allocating and freeing large numbers of
>> 4-byte blocks took twenty times longer using malloc/free (and probably
>> took 2-4 times as much space) than using a special allocator.

> Bartc: Are you sure of this? What I really wanted to ask: Is it
> reasonable to plan for saving 50% of memory allocation time by rewriting
> special functions for same ? If speedup can be 20X this is amazing.

Don't get too excited: if your code does nothing except allocate/free blocks
of memory, and most allocations are of a particularly simple type, then
you might get good speedups with a custom allocator.

In practice allocation patterns can be a bit more complex, and you can end
up wasting time doing what malloc/free already does more efficiently than 
you can.

You need to do more tests as to what overheads currently are. 50% time
saving is not worthwhile if allocation only takes up 1% of runtime. (And
then remember each implementation will be faster or slower.)

-- 
Bartc 

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

#4264

On 5/18/2011 1:11 PM, Pushpa wrote:
> BartC writes:
>> [...]
>> I've just done a test where allocating and freeing large numbers of
>> 4-byte blocks took twenty times longer using malloc/free (and probably
>> took 2-4 times as much space) than using a special allocator.
>>
>> How significant this is depends on the application, but I don't think
>> you can just dismiss such an allocator.
>
> Bartc: Are you sure of this? What I really wanted to ask: Is it
> reasonable to plan for saving 50% of memory allocation time by rewriting
> special functions for same ? If speedup can be 20X this is amazing.

     It gets back to what I mentioned before: If you know something
important about your allocations, and you can think of a way to
exploit that knowledge, then you may be able to write code that is
better specialized for your allocation patterns than general-purpose
malloc().

     But in your original post you wrote "I am talking about general
purpose applications," which can be read as "I have no exploitable
knowledge about the memory usage patterns."  In that case, the issue
collapses to "Can I, myself, write a better general-purpose malloc()
package than the vendors' experts?"  As I also pointed out, this is
sometimes possible when the vendor has given the job to tyros and not
to experts.  Nowadays I suspect such lame vendors are not exactly
thick upon the ground; in fact, the one I know of has disappeared.

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

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

#4237

"BartC" <bc@freeuk.com> writes:

> "Ben Pfaff" <blp@cs.stanford.edu> wrote in message
> news:87aael3xw1.fsf@blp.benpfaff.org...
<snip>
>> According to an academic study I read some time ago, there is
>> rarely any significant advantage to special-purpose memory
>> allocators.  In a quick online search, I didn't find a reference
>> to this paper, but perhaps someone else here has a copy of it.
>
> I've just done a test where allocating and freeing large numbers of
> 4-byte blocks took twenty times longer using malloc/free (and probably
> took 2-4 
> times as much space) than using a special allocator.

That's interesting, but of limited value unless you can give more
details.  Ideally, can you post the code?  That way it can tried on
different systems with different C libraries.

At least say what the "special allocator" is.  Relative speed up must be
relative to something known, not something mysterious.

> How significant this is depends on the application, but I don't think
> you can just dismiss such an allocator.

But no one else can consider it either since we don't know what it is.

-- 
Ben.

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

#4246

On Wed, May 18, 2011 at 07:34:28PM +0100, Ben Bacarisse wrote:
> "BartC" <bc@freeuk.com> writes:
> 
> > "Ben Pfaff" <blp@cs.stanford.edu> wrote in message
> > news:87aael3xw1.fsf@blp.benpfaff.org...
> <snip>
> >> According to an academic study I read some time ago, there is
> >> rarely any significant advantage to special-purpose memory
> >> allocators.  In a quick online search, I didn't find a reference
> >> to this paper, but perhaps someone else here has a copy of it.
> >
> > I've just done a test where allocating and freeing large numbers of
> > 4-byte blocks took twenty times longer using malloc/free (and probably
> > took 2-4 
> > times as much space) than using a special allocator.
> 
> That's interesting, but of limited value unless you can give more
> details.  Ideally, can you post the code?  That way it can tried on
> different systems with different C libraries.
> 
> At least say what the "special allocator" is.  Relative speed up must be
> relative to something known, not something mysterious.
> 
> > How significant this is depends on the application, but I don't think
> > you can just dismiss such an allocator.
> 
> But no one else can consider it either since we don't know what it is.

It's probably something similar to what I use occasionally:

struct arena_head {
	int	obj_size;
	int	arena_size; /* obj_size count */
	char *	arena;
	int	free;
	int	free_list;
};

There's a function that mallocs the header and data area, and
initializes the free list, which in my case is a linked list of
integers stored in the first word of each arena slot.  The allocator
comes in two varieties:  one that will realloc() the arena
automatically when the free slots are exhausted, and one that just
returns -1 if the arena is exhausted.

#define arena_obj_addr(x, n) ((void *) *(&p->arena[n * x->obj_size]))

arena_qa(struct arena_head *x)
{
   int n;

   n = x->free_list;

   if(n != -1) {
      x->free_list = *((int *) arena_obj_addr(x, n));
      x->free--;
   }

   return(n);
}   

void arena_free(struct arena_head *p, int n)
{
   *((int *) arena_obj_addr(p, n)) = p->free_list;
   p->free_list = n;
   p->free++;

   return;
}

I haven't measured it's performance against malloc() just yet, but it
must be something like an order of magnitude faster than malloc.  I
spent some time to make it a little more flexible than the pared-down
version here, such as including an option to clear each slot when it
is freed automatically, and so on.  In a debugger, it's fairly easy to
inspect the book-keeping and you can output a diagnostic message if
you destroy the arena while there are still allocated slots, which
identifies memory leaks.

When I read up on the malloc() implementation in glibc (a few years
ago), it stated that the length of the allocation was stored in the
32-bit word immediately prior to the pointer returned by malloc (on
x86) and there were additional padding bytes, probably a maximum of
three on x86 (not sure how true this is today).  So, a four-byte object
size would require eight bytes minimum storage.  When you're dealing
with many hundreds of thousands or even millions of allocations, that
might be the difference between keeping your data set in memory, or
going into swap space.  For even 30% savings in memory, not to mention
speed, this is a real win.

I would propose that this is a simple example of a 'better algorithm'.
malloc() is designed to handle the general case of arbitrary
allocations occurring with arbitrary ordering.  When you know you're
going to use many of the same size object it is easy to adapt the
algorithm to use this arrangement, and for this special case it is
fast and compact.  What is the counterargument against using this kind
of structure?



Regards,

Uncle Steve

-- 
Should a professional politician be charged with molestation if he
kisses babies while attending political rallies?

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

#4257

Uncle Steve <stevet810@gmail.com> writes:

> On Wed, May 18, 2011 at 07:34:28PM +0100, Ben Bacarisse wrote:
>> "BartC" <bc@freeuk.com> writes:
>> 
>> > "Ben Pfaff" <blp@cs.stanford.edu> wrote in message
>> > news:87aael3xw1.fsf@blp.benpfaff.org...
>> <snip>
>> >> According to an academic study I read some time ago, there is
>> >> rarely any significant advantage to special-purpose memory
>> >> allocators.  In a quick online search, I didn't find a reference
>> >> to this paper, but perhaps someone else here has a copy of it.
>> >
>> > I've just done a test where allocating and freeing large numbers of
>> > 4-byte blocks took twenty times longer using malloc/free (and probably
>> > took 2-4 
>> > times as much space) than using a special allocator.
>> 
>> That's interesting, but of limited value unless you can give more
>> details.  Ideally, can you post the code?  That way it can tried on
>> different systems with different C libraries.
>> 
>> At least say what the "special allocator" is.  Relative speed up must be
>> relative to something known, not something mysterious.
>> 
>> > How significant this is depends on the application, but I don't think
>> > you can just dismiss such an allocator.
>> 
>> But no one else can consider it either since we don't know what it is.
>
> It's probably something similar to what I use occasionally:

Yes, similar but even simpler.

<snip code>
> I haven't measured it's performance against malloc() just yet, but it
> must be something like an order of magnitude faster than malloc.

I am guessing you don't have a background in the sciences!

<snip>
> I would propose that this is a simple example of a 'better algorithm'.

I am glad that's in 'scare quotes'.  I don't really want to get into a
discussion of whether a special-case algorithm is better than a general
one.  It depends on your metrics, no doubt.  What I'd really like is
some data, and even better than that would be some code I could try to
see how general the benefit is (across systems) for some specific
special-purpose allocator.

> malloc() is designed to handle the general case of arbitrary
> allocations occurring with arbitrary ordering.  When you know you're
> going to use many of the same size object it is easy to adapt the
> algorithm to use this arrangement, and for this special case it is
> fast and compact.  What is the counterargument against using this kind
> of structure?

(a) You have to write it and debug it.  The code you posted had bugs,
but that's probably because it was pulled out of context to illustrate
the idea.  (BTW, I've been around the block long enough that you could
just have said that it's a free list of fixed size objects).

(b) You might also have to port it (see the problem that BartC's code
had on my machine for example).

(c) Other people might have to learn about the interface (and maybe
persuade themselves of the implementation) if they come to maintain code
that uses it.  Every C programmer know malloc(...).  You code, for
example, does not allocate and free using pointers -- the functions take
and return an int.  This is perfectly logical, but it will take some
getting used for the maintainer.

These all boil down to "more code".  The question remains, though, about
the benefits.  It would be very helpful to have the speed benefit
quantified.

-- 
Ben.

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

#4267

On Thu, May 19, 2011 at 12:26:15AM +0100, Ben Bacarisse wrote:
> Uncle Steve <stevet810@gmail.com> writes:
> 
> > On Wed, May 18, 2011 at 07:34:28PM +0100, Ben Bacarisse wrote:
> >> "BartC" <bc@freeuk.com> writes:
> >> 
> >> > "Ben Pfaff" <blp@cs.stanford.edu> wrote in message
> >> > news:87aael3xw1.fsf@blp.benpfaff.org...
> >> <snip>
> >> >> According to an academic study I read some time ago, there is
> >> >> rarely any significant advantage to special-purpose memory
> >> >> allocators.  In a quick online search, I didn't find a reference
> >> >> to this paper, but perhaps someone else here has a copy of it.
> >> >
> >> > I've just done a test where allocating and freeing large numbers of
> >> > 4-byte blocks took twenty times longer using malloc/free (and probably
> >> > took 2-4 
> >> > times as much space) than using a special allocator.
> >> 
> >> That's interesting, but of limited value unless you can give more
> >> details.  Ideally, can you post the code?  That way it can tried on
> >> different systems with different C libraries.
> >> 
> >> At least say what the "special allocator" is.  Relative speed up must be
> >> relative to something known, not something mysterious.
> >> 
> >> > How significant this is depends on the application, but I don't think
> >> > you can just dismiss such an allocator.
> >> 
> >> But no one else can consider it either since we don't know what it is.
> >
> > It's probably something similar to what I use occasionally:
> 
> Yes, similar but even simpler.
> 
> <snip code>
> > I haven't measured it's performance against malloc() just yet, but it
> > must be something like an order of magnitude faster than malloc.
> 
> I am guessing you don't have a background in the sciences!

Not really.  Science fiction doesn't really count.  Real science is
time-consuming, and I just don't have enough free leisure hours in the
day.
 
> <snip>
> > I would propose that this is a simple example of a 'better algorithm'.
> 
> I am glad that's in 'scare quotes'.  I don't really want to get into a
> discussion of whether a special-case algorithm is better than a general
> one.  It depends on your metrics, no doubt.  What I'd really like is
> some data, and even better than that would be some code I could try to
> see how general the benefit is (across systems) for some specific
> special-purpose allocator.

Hey, the code I wrote there is almost trivial to test.  I don't know
why you're so keen to get numbers on it, part of my reason for not
having those numbers is that it's more meaningful to measure the
performance of real code that's using the allocator.  Besides, what
I've done here has probably been studied to death some time way back
in the sixties or seventies.  I don't have convenient access to a
university library account, so an abstract search is problematic for
me.  You'll probably get buried in citations if you try this route.

Anyways, as I'm not an actual working scientist, measurement of every little
thing in my programs isn't much of a priority.  If it is for you,
actually implementing the arena_open() and arena_close() will take
less time than setting up your test bench.

> > malloc() is designed to handle the general case of arbitrary
> > allocations occurring with arbitrary ordering.  When you know you're
> > going to use many of the same size object it is easy to adapt the
> > algorithm to use this arrangement, and for this special case it is
> > fast and compact.  What is the counterargument against using this kind
> > of structure?
> 
> (a) You have to write it and debug it.  The code you posted had bugs,
> but that's probably because it was pulled out of context to illustrate
> the idea.  (BTW, I've been around the block long enough that you could
> just have said that it's a free list of fixed size objects).

Probably, but people with less experience might not have appreciated the
simplicity of the algorithm if it was full of object padding
calculations, and all the little bits that go along with it.  Of
course I edited for brevity.  In this newsgroup, when someone posts a
few screens full of code it takes time to read it.  I don't think it
would have been better if I had posted the entire source file in this
instance.
 
> (b) You might also have to port it (see the problem that BartC's code
> had on my machine for example).
> 
> (c) Other people might have to learn about the interface (and maybe
> persuade themselves of the implementation) if they come to maintain code
> that uses it.  Every C programmer know malloc(...).  You code, for
> example, does not allocate and free using pointers -- the functions take
> and return an int.  This is perfectly logical, but it will take some
> getting used for the maintainer.

Oh, absolutely.  Using integers as a sort of offset from a base is
the kind of thing more common to assembly language programmers, but
even in C it's a common idiom to use an array index, this is instead a
base + offset arrangement.  Stated that way, it is easy to understand
what is going on in the code.  Not much of an intellectual burden.
 
> These all boil down to "more code".  The question remains, though, about
> the benefits.  It would be very helpful to have the speed benefit
> quantified.

I guess.  If your question bugs me enough I'll think about setting
aside a couple of hours on the weekend.



Regards,

Uncle Steve

-- 
Should a professional politician be charged with molestation if he
kisses babies while attending political rallies?

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

#4268

On 05/18/2011 09:25 PM, Uncle Steve wrote:
> On Thu, May 19, 2011 at 12:26:15AM +0100, Ben Bacarisse wrote:
>> Uncle Steve <stevet810@gmail.com> writes:
>>
...
>>> I haven't measured it's performance against malloc() just yet, but it
>>> must be something like an order of magnitude faster than malloc.
>>
>> I am guessing you don't have a background in the sciences!
> 
> Not really.  Science fiction doesn't really count.  Real science is
> time-consuming, and I just don't have enough free leisure hours in the
> day.

If you don't have sufficient spare time to test whether or not your
custom allocator actually significantly improves the speed of your
programs, you don't have enough spare time to justify wasting it
producing untested custom allocators.

...
> Hey, the code I wrote there is almost trivial to test.  I don't know
> why you're so keen to get numbers on it,

He's not - the key point is that you SHOULD be. If it's indeed trivial
to test, you should have done so already. Until you have those numbers,
you can't be sure whether or not your custom allocator was a complete
waste of time.

...
> course I edited for brevity.  In this newsgroup, when someone posts a
> few screens full of code it takes time to read it.  I don't think it
> would have been better if I had posted the entire source file in this
> instance.

Example code that has, at the very least, been compiled, and preferably
tested, wastes a lot less of a reviewer's time than code with a variety
of miscellaneous uncaught bugs. The reviewer has to waste time trying to
figure out whether those are actually bugs, or features.

...
> Oh, absolutely.  Using integers as a sort of offset from a base is
> the kind of thing more common to assembly language programmers, but
> even in C it's a common idiom to use an array index,

It's not as common as you seem to think.

-- 
James Kuyper

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

#4343

On Wed, May 18, 2011 at 09:38:05PM -0400, James Kuyper wrote:
> On 05/18/2011 09:25 PM, Uncle Steve wrote:
> > On Thu, May 19, 2011 at 12:26:15AM +0100, Ben Bacarisse wrote:
> >> Uncle Steve <stevet810@gmail.com> writes:
> >>
> ...
> >>> I haven't measured it's performance against malloc() just yet, but it
> >>> must be something like an order of magnitude faster than malloc.
> >>
> >> I am guessing you don't have a background in the sciences!
> > 
> > Not really.  Science fiction doesn't really count.  Real science is
> > time-consuming, and I just don't have enough free leisure hours in the
> > day.
> 
> If you don't have sufficient spare time to test whether or not your
> custom allocator actually significantly improves the speed of your
> programs, you don't have enough spare time to justify wasting it
> producing untested custom allocators.

That's a little bit presumptuous.  Are you suddenly in charge of my
development schedule?  I must have missed the memo.  Anyways, I think
it's valid to say that some things are understandable by 'inspection',
as I think they say in some math texts.
 
> ...
> > Hey, the code I wrote there is almost trivial to test.  I don't know
> > why you're so keen to get numbers on it,
> 
> He's not - the key point is that you SHOULD be. If it's indeed trivial
> to test, you should have done so already. Until you have those numbers,
> you can't be sure whether or not your custom allocator was a complete
> waste of time.

The one previous to that may have been, but I didn't test it either.
Instead, I wrote the version I'm using now.  BTW, I do all my code
development in a very limited amount of free time.  You seem to be
saying that as I am talking about the algorithm in a public newsgroup,
that I should have also proved it in the lab and in the field, not to
mention publishing all the testing data and methodologies.

As I mentioned previously I'm not a working scientist, even if I know
some of what they do and how they go about it.
 
> ...
> > course I edited for brevity.  In this newsgroup, when someone posts a
> > few screens full of code it takes time to read it.  I don't think it
> > would have been better if I had posted the entire source file in this
> > instance.
> 
> Example code that has, at the very least, been compiled, and preferably
> tested, wastes a lot less of a reviewer's time than code with a variety
> of miscellaneous uncaught bugs. The reviewer has to waste time trying to
> figure out whether those are actually bugs, or features.

Are we 'reviewing' code in this newsgroup?  I thought we were
discussing it.
 
> ...
> > Oh, absolutely.  Using integers as a sort of offset from a base is
> > the kind of thing more common to assembly language programmers, but
> > even in C it's a common idiom to use an array index,
> 
> It's not as common as you seem to think.

I don't really know how common it is, so you're already ahead of me on
that score.



Regards,

Uncle Steve

-- 
Should a professional politician be charged with molestation if he
kisses babies while attending political rallies?

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

#4413

On 05/19/2011 02:11 PM, Uncle Steve wrote:
> On Wed, May 18, 2011 at 09:38:05PM -0400, James Kuyper wrote:
>> On 05/18/2011 09:25 PM, Uncle Steve wrote:
...
>> If you don't have sufficient spare time to test whether or not your
>> custom allocator actually significantly improves the speed of your
>> programs, you don't have enough spare time to justify wasting it
>> producing untested custom allocators.
> 
> That's a little bit presumptuous.  Are you suddenly in charge of my
> development schedule?  I must have missed the memo.

You're right - I should have expressed that differently: if you have
enough spare time to write your allocator, you're going to receive a
serious lack of sympathy when you complain about not having enough time
to bother testing it. You are, of course, free to ignore the ridicule
you deserve for prioritizing your time that way.

...
> development in a very limited amount of free time.  You seem to be
> saying that as I am talking about the algorithm in a public newsgroup,
> that I should have also proved it in the lab and in the field, not to
> mention publishing all the testing data and methodologies.

What I said has nothing to do with the fact that this is a public
newsgroup. Even if you're just doing it for yourself, it's a serious
waste of your time (which you are, of course, completely free to decide
to waste) to go to the trouble of building a custom allocator without
bothering to test whether you gained any benefit from doing so.

...
> Are we 'reviewing' code in this newsgroup?  I thought we were
> discussing it.

I don't see a distinction. I don't see how you could discuss code in any
meaningful sense without first reviewing it - otherwise, how would you
know what it was that you were discussing? Perhaps you thought I was
using the word "review" strictly in some more formal sense?

>> ...
>>> Oh, absolutely.  Using integers as a sort of offset from a base is
>>> the kind of thing more common to assembly language programmers, but
>>> even in C it's a common idiom to use an array index,
>>
>> It's not as common as you seem to think.
> 
> I don't really know how common it is, so you're already ahead of me on
> that score.

C is notorious for the ubiquity of pointers in contexts where other
languages would use integer indices.
-- 
James Kuyper

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

#4434

On Thu, May 19, 2011 at 10:55:35PM -0400, James Kuyper wrote:
> On 05/19/2011 02:11 PM, Uncle Steve wrote:
> > On Wed, May 18, 2011 at 09:38:05PM -0400, James Kuyper wrote:
> >> On 05/18/2011 09:25 PM, Uncle Steve wrote:
> ...
> >> If you don't have sufficient spare time to test whether or not your
> >> custom allocator actually significantly improves the speed of your
> >> programs, you don't have enough spare time to justify wasting it
> >> producing untested custom allocators.
> > 
> > That's a little bit presumptuous.  Are you suddenly in charge of my
> > development schedule?  I must have missed the memo.
> 
> You're right - I should have expressed that differently: if you have
> enough spare time to write your allocator, you're going to receive a
> serious lack of sympathy when you complain about not having enough time
> to bother testing it. You are, of course, free to ignore the ridicule
> you deserve for prioritizing your time that way.

The main reason I didn't time the thing previously is that the
allocator will usually be a small fraction of the total 'k' for any
given application.  A binary tree using the allocator is going to
spend more time doing comparisons on an insert than the cost of
allocating the node.  I've known this for a while.

Measuring the performance of a binary tree algorithm is another kettle
of fish altogether, and if I were making similar claims about one, I
think there'd be better grounds for criticism in that case.
Personally, I think that a demand for test data in a trivial case such
as this is a little harsh.  If a programmer is making claims about
algorithm performance in a real-world application, that is another
thing altogether, an in that case you would be perfectly justified in
demanding test results.  But on Usenet, and about something that is
available to inspection by competent individuals...  Not so much.

> > development in a very limited amount of free time.  You seem to be
> > saying that as I am talking about the algorithm in a public newsgroup,
> > that I should have also proved it in the lab and in the field, not to
> > mention publishing all the testing data and methodologies.
> 
> What I said has nothing to do with the fact that this is a public
> newsgroup. Even if you're just doing it for yourself, it's a serious
> waste of your time (which you are, of course, completely free to decide
> to waste) to go to the trouble of building a custom allocator without
> bothering to test whether you gained any benefit from doing so.

I have no qualms about testing and verification, I just did not think
it was quite so important in this particular instance.

> > Are we 'reviewing' code in this newsgroup?  I thought we were
> > discussing it.
> 
> I don't see a distinction. I don't see how you could discuss code in any
> meaningful sense without first reviewing it - otherwise, how would you
> know what it was that you were discussing? Perhaps you thought I was
> using the word "review" strictly in some more formal sense?

I thought you may have been implying association with a 'peer review'
process, which is necessarily much more formal.  The discussion of a
topic would generally imply familiarity with its material,
necessitating /a/ review of it, but that says nothing about the degree
of analytical engagement.  In a public newsgroup, I would anticipate a
more casual approach to the discussion of an algorithm or fragments of
same.

I have posted a very shaky test-harness (written in less than one
hour) that is exclusively intended to show the gross performance
improvement over the 'standard' malloc(), whatever that may be on your
platform.  That is all, and I 'proved' the validity of my hypothesis,
so far as that goes.  If we were discussing real computer science,
post latency would be on the order of days or weeks, not the minutes
or hours turnaround generally expected in a Usenet thread.
 
> >>> Oh, absolutely.  Using integers as a sort of offset from a base is
> >>> the kind of thing more common to assembly language programmers, but
> >>> even in C it's a common idiom to use an array index,
> >>
> >> It's not as common as you seem to think.
> > 
> > I don't really know how common it is, so you're already ahead of me on
> > that score.
> 
> C is notorious for the ubiquity of pointers in contexts where other
> languages would use integer indices.

Which is why I get the impression that some of you are a little
puzzled by my use of integer-multiplied offsets from the array base?
I would have thought that a more common idiom merely for the fact that
it is such a useful arrangement in circumstances where the data is of
a uniform size.  C makes this easy.  In another language, I might have
had to maintain the free list with a bitmap, or some other
contrivance.  For most people this will be a non-issue because they
will use the language-supplied libraries for everything, and they'll
never have to worry about the implementation details of their binary
tree structures, or whatever.

C is different in that respect, and so naturally I've thought about
methods for reducing algorithm complexity and memory requirements.  If
I use this algorithm consistently in my new programs I lose no coding
time in doing so, as opposed to trying to jam it in to an already
existing application that uses malloc.  Even if it only improves a
real-world algorithm by five percent, I have probably lost nothing by
using it, and the educational value derived from writing and using it
is 100% free.

I've added comp.programming to the Newsgroups: line.  I think this
discussion is not so much about C, the language as it is about C
programming technique or algorithm design.



Regards,

Uncle Steve

-- 
Should a professional politician be charged with molestation if he
kisses babies while attending political rallies?

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

#4275

Uncle Steve <stevet810@gmail.com> writes:

> On Thu, May 19, 2011 at 12:26:15AM +0100, Ben Bacarisse wrote:
>> Uncle Steve <stevet810@gmail.com> writes:
>> 
>> > On Wed, May 18, 2011 at 07:34:28PM +0100, Ben Bacarisse wrote:
>> >> "BartC" <bc@freeuk.com> writes:
>> >> 
>> >> > "Ben Pfaff" <blp@cs.stanford.edu> wrote in message
>> >> > news:87aael3xw1.fsf@blp.benpfaff.org...
>> >> <snip>
>> >> >> According to an academic study I read some time ago, there is
>> >> >> rarely any significant advantage to special-purpose memory
>> >> >> allocators.  In a quick online search, I didn't find a reference
>> >> >> to this paper, but perhaps someone else here has a copy of it.
>> >> >
>> >> > I've just done a test where allocating and freeing large numbers of
>> >> > 4-byte blocks took twenty times longer using malloc/free (and probably
>> >> > took 2-4 
>> >> > times as much space) than using a special allocator.
>> >> 
>> >> That's interesting, but of limited value unless you can give more
>> >> details.  Ideally, can you post the code?  That way it can tried on
>> >> different systems with different C libraries.
>> >> 
>> >> At least say what the "special allocator" is.  Relative speed up must be
>> >> relative to something known, not something mysterious.
>> >> 
>> >> > How significant this is depends on the application, but I don't think
>> >> > you can just dismiss such an allocator.
>> >> 
>> >> But no one else can consider it either since we don't know what it is.
>> >
>> > It's probably something similar to what I use occasionally:
>> 
>> Yes, similar but even simpler.
>> 
>> <snip code>
>> > I haven't measured it's performance against malloc() just yet, but it
>> > must be something like an order of magnitude faster than malloc.
>> 
>> I am guessing you don't have a background in the sciences!
>
> Not really.  Science fiction doesn't really count.  Real science is
> time-consuming, and I just don't have enough free leisure hours in the
> day.
>  
>> <snip>
>> > I would propose that this is a simple example of a 'better algorithm'.
>> 
>> I am glad that's in 'scare quotes'.  I don't really want to get into a
>> discussion of whether a special-case algorithm is better than a general
>> one.  It depends on your metrics, no doubt.  What I'd really like is
>> some data, and even better than that would be some code I could try to
>> see how general the benefit is (across systems) for some specific
>> special-purpose allocator.
>
> Hey, the code I wrote there is almost trivial to test.  I don't know
> why you're so keen to get numbers on it, part of my reason for not
> having those numbers is that it's more meaningful to measure the
> performance of real code that's using the allocator.  Besides, what
> I've done here has probably been studied to death some time way back
> in the sixties or seventies.  I don't have convenient access to a
> university library account, so an abstract search is problematic for
> me.  You'll probably get buried in citations if you try this route.

I think this sort of thing has to be done every generation.  I doubt
that conclusions drawn on a PDP-11 or an IBM 360 relate to my multi-core
multi-level cache machine.  I've seen the situation change.  At one
point I took out a freelist allocator like yours from a function
language implementation of mine because it added very little to the
performance.  Maybe I would be changing that ifdef macro now.  Only
measurements can tell, and I can't test that code any more -- I seem to
have lost it into the big bit bucket in the sky.

Even if the general rules are the same (specific-case allocation being
cheaper than general-case) the thing that prompted my reply was a
number: 20 times.  I'd like to check that out on my system.

<snip>
>> > What is the counterargument against using this kind
>> > of structure?
>> 
>> (a) You have to write it and debug it.  The code you posted had bugs,
>> but that's probably because it was pulled out of context to illustrate
>> the idea.  (BTW, I've been around the block long enough that you could
>> just have said that it's a free list of fixed size objects).
>
> Probably, but people with less experience might not have appreciated the
> simplicity of the algorithm if it was full of object padding
> calculations, and all the little bits that go along with it.  Of
> course I edited for brevity.

You edited in some bugs too:

| #define arena_obj_addr(x, n) ((void *) *(&p->arena[n * x->obj_size]))

'p' can't be right here.  It must be 'x', yes?  The result of the
expression is a char converted to void *.  That can't be right either.
presumably the '*' in front of the '(&' should not be there.  (And I'd
add parentheses round all the macro arguments in the body.)

<snip>
>> (c) Other people might have to learn about the interface (and maybe
>> persuade themselves of the implementation) if they come to maintain code
>> that uses it.  Every C programmer know malloc(...).  You code, for
>> example, does not allocate and free using pointers -- the functions take
>> and return an int.  This is perfectly logical, but it will take some
>> getting used for the maintainer.
>
> Oh, absolutely.  Using integers as a sort of offset from a base is
> the kind of thing more common to assembly language programmers, but
> even in C it's a common idiom to use an array index, this is instead a
> base + offset arrangement.  Stated that way, it is easy to understand
> what is going on in the code.  Not much of an intellectual burden.

I don't thinks it's a common idiom at all and I've see a lot of C over
the years.  The last time I saw it was in Gregory Chaitin's tiny Lisp
interpreter that he's used in his books and courses.  It's not exactly
idiomatic C, but then he has bigger fish to fry.

<snip>
-- 
Ben.

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

#4346

On Thu, May 19, 2011 at 03:22:18AM +0100, Ben Bacarisse wrote:
> Uncle Steve <stevet810@gmail.com> writes:
> 
> > On Thu, May 19, 2011 at 12:26:15AM +0100, Ben Bacarisse wrote:
> >> Uncle Steve <stevet810@gmail.com> writes:
> >> 
> >> > On Wed, May 18, 2011 at 07:34:28PM +0100, Ben Bacarisse wrote:
> >> >> "BartC" <bc@freeuk.com> writes:
> >> >> 
> >> >> > "Ben Pfaff" <blp@cs.stanford.edu> wrote in message
> >> >> > news:87aael3xw1.fsf@blp.benpfaff.org...
> >> >> <snip>
> >> >> >> According to an academic study I read some time ago, there is
> >> >> >> rarely any significant advantage to special-purpose memory
> >> >> >> allocators.  In a quick online search, I didn't find a reference
> >> >> >> to this paper, but perhaps someone else here has a copy of it.
> >> >> >
> >> >> > I've just done a test where allocating and freeing large numbers of
> >> >> > 4-byte blocks took twenty times longer using malloc/free (and probably
> >> >> > took 2-4 
> >> >> > times as much space) than using a special allocator.
> >> >> 
> >> >> That's interesting, but of limited value unless you can give more
> >> >> details.  Ideally, can you post the code?  That way it can tried on
> >> >> different systems with different C libraries.
> >> >> 
> >> >> At least say what the "special allocator" is.  Relative speed up must be
> >> >> relative to something known, not something mysterious.
> >> >> 
> >> >> > How significant this is depends on the application, but I don't think
> >> >> > you can just dismiss such an allocator.
> >> >> 
> >> >> But no one else can consider it either since we don't know what it is.
> >> >
> >> > It's probably something similar to what I use occasionally:
> >> 
> >> Yes, similar but even simpler.
> >> 
> >> <snip code>
> >> > I haven't measured it's performance against malloc() just yet, but it
> >> > must be something like an order of magnitude faster than malloc.
> >> 
> >> I am guessing you don't have a background in the sciences!
> >
> > Not really.  Science fiction doesn't really count.  Real science is
> > time-consuming, and I just don't have enough free leisure hours in the
> > day.
> >  
> >> <snip>
> >> > I would propose that this is a simple example of a 'better algorithm'.
> >> 
> >> I am glad that's in 'scare quotes'.  I don't really want to get into a
> >> discussion of whether a special-case algorithm is better than a general
> >> one.  It depends on your metrics, no doubt.  What I'd really like is
> >> some data, and even better than that would be some code I could try to
> >> see how general the benefit is (across systems) for some specific
> >> special-purpose allocator.
> >
> > Hey, the code I wrote there is almost trivial to test.  I don't know
> > why you're so keen to get numbers on it, part of my reason for not
> > having those numbers is that it's more meaningful to measure the
> > performance of real code that's using the allocator.  Besides, what
> > I've done here has probably been studied to death some time way back
> > in the sixties or seventies.  I don't have convenient access to a
> > university library account, so an abstract search is problematic for
> > me.  You'll probably get buried in citations if you try this route.
> 
> I think this sort of thing has to be done every generation.  I doubt
> that conclusions drawn on a PDP-11 or an IBM 360 relate to my multi-core
> multi-level cache machine.  I've seen the situation change.  At one
> point I took out a freelist allocator like yours from a function
> language implementation of mine because it added very little to the
> performance.  Maybe I would be changing that ifdef macro now.  Only
> measurements can tell, and I can't test that code any more -- I seem to
> have lost it into the big bit bucket in the sky.
> 
> Even if the general rules are the same (specific-case allocation being
> cheaper than general-case) the thing that prompted my reply was a
> number: 20 times.  I'd like to check that out on my system.
> 
> <snip>
> >> > What is the counterargument against using this kind
> >> > of structure?
> >> 
> >> (a) You have to write it and debug it.  The code you posted had bugs,
> >> but that's probably because it was pulled out of context to illustrate
> >> the idea.  (BTW, I've been around the block long enough that you could
> >> just have said that it's a free list of fixed size objects).
> >
> > Probably, but people with less experience might not have appreciated the
> > simplicity of the algorithm if it was full of object padding
> > calculations, and all the little bits that go along with it.  Of
> > course I edited for brevity.
> 
> You edited in some bugs too:
> 
> | #define arena_obj_addr(x, n) ((void *) *(&p->arena[n * x->obj_size]))
> 
> 'p' can't be right here.  It must be 'x', yes?  The result of the
> expression is a char converted to void *.  That can't be right either.
> presumably the '*' in front of the '(&' should not be there.  (And I'd
> add parentheses round all the macro arguments in the body.)

You're correct.  The original function definitions have extra
convenience macros, and the macro variables are protected from
side-effects, etc.  Of course it should be:

| #define arena_obj_addr(x, n) ((void *) *(&x->arena[n * x->obj_size]))
 
> <snip>
> >> (c) Other people might have to learn about the interface (and maybe
> >> persuade themselves of the implementation) if they come to maintain code
> >> that uses it.  Every C programmer know malloc(...).  You code, for
> >> example, does not allocate and free using pointers -- the functions take
> >> and return an int.  This is perfectly logical, but it will take some
> >> getting used for the maintainer.
> >
> > Oh, absolutely.  Using integers as a sort of offset from a base is
> > the kind of thing more common to assembly language programmers, but
> > even in C it's a common idiom to use an array index, this is instead a
> > base + offset arrangement.  Stated that way, it is easy to understand
> > what is going on in the code.  Not much of an intellectual burden.
> 
> I don't thinks it's a common idiom at all and I've see a lot of C over
> the years.  The last time I saw it was in Gregory Chaitin's tiny Lisp
> interpreter that he's used in his books and courses.  It's not exactly
> idiomatic C, but then he has bigger fish to fry.

I take it you're refering to hiding the integer in the body of the
arena object for the free list via a slightly clever cast?  One of the
strengths of C, although it is a weakness as well since the conversion
of pointer types introduces complexities that can easily trip you up.



Regards,

Uncle Steve

-- 
Should a professional politician be charged with molestation if he
kisses babies while attending political rallies?

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

#4397

Uncle Steve <stevet810@gmail.com> writes:

> On Thu, May 19, 2011 at 03:22:18AM +0100, Ben Bacarisse wrote:
>> Uncle Steve <stevet810@gmail.com> writes:
>> 
>> > On Thu, May 19, 2011 at 12:26:15AM +0100, Ben Bacarisse wrote:
<snip>
>> You edited in some bugs too:
>> 
>> | #define arena_obj_addr(x, n) ((void *) *(&p->arena[n * x->obj_size]))
>> 
>> 'p' can't be right here.  It must be 'x', yes?  The result of the
>> expression is a char converted to void *.  That can't be right either.
>> presumably the '*' in front of the '(&' should not be there.  (And I'd
>> add parentheses round all the macro arguments in the body.)
>
> You're correct.  The original function definitions have extra
> convenience macros, and the macro variables are protected from
> side-effects, etc.  Of course it should be:
>
> | #define arena_obj_addr(x, n) ((void *) *(&x->arena[n * x->obj_size]))

x->arena is a char *.  x->arena[...] is a char.  &x->arena[...] is a
char * again.  *(&x->arena[...]) is back to type char.  You can't want
to convert that to a void * and return it.  I think the middle * should
not be there.

<snip>
>> > Oh, absolutely.  Using integers as a sort of offset from a base is
>> > the kind of thing more common to assembly language programmers, but
>> > even in C it's a common idiom to use an array index, this is instead a
>> > base + offset arrangement.  Stated that way, it is easy to understand
>> > what is going on in the code.  Not much of an intellectual burden.
>> 
>> I don't thinks it's a common idiom at all and I've see a lot of C over
>> the years.  The last time I saw it was in Gregory Chaitin's tiny Lisp
>> interpreter that he's used in his books and courses.  It's not exactly
>> idiomatic C, but then he has bigger fish to fry.
>
> I take it you're refering to hiding the integer in the body of the
> arena object for the free list via a slightly clever cast?  One of the
> strengths of C, although it is a weakness as well since the conversion
> of pointer types introduces complexities that can easily trip you up.

I don't think that's what I meant.  I was referring to the more dramatic
difference: your free and allocate functions take and return ints not
pointers.

-- 
Ben.

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

#4402

On Thu, May 19, 2011 at 11:51:33PM +0100, Ben Bacarisse wrote:
> Uncle Steve <stevet810@gmail.com> writes:
> 
> > On Thu, May 19, 2011 at 03:22:18AM +0100, Ben Bacarisse wrote:
> >> Uncle Steve <stevet810@gmail.com> writes:
> >> 
> >> > On Thu, May 19, 2011 at 12:26:15AM +0100, Ben Bacarisse wrote:
> <snip>
> >> You edited in some bugs too:
> >> 
> >> | #define arena_obj_addr(x, n) ((void *) *(&p->arena[n * x->obj_size]))
> >> 
> >> 'p' can't be right here.  It must be 'x', yes?  The result of the
> >> expression is a char converted to void *.  That can't be right either.
> >> presumably the '*' in front of the '(&' should not be there.  (And I'd
> >> add parentheses round all the macro arguments in the body.)
> >
> > You're correct.  The original function definitions have extra
> > convenience macros, and the macro variables are protected from
> > side-effects, etc.  Of course it should be:
> >
> > | #define arena_obj_addr(x, n) ((void *) *(&x->arena[n * x->obj_size]))
> 
> x->arena is a char *.  x->arena[...] is a char.  &x->arena[...] is a
> char * again.  *(&x->arena[...]) is back to type char.  You can't want
> to convert that to a void * and return it.  I think the middle * should
> not be there.

Yeah, I must have mistyped something when I originally wrote it.  In 
your favor is a request for compilable code, which I have finally
supplied in another message.  Maybe that would be a better basis on
which to make comments.

> <snip>
> >> > Oh, absolutely.  Using integers as a sort of offset from a base is
> >> > the kind of thing more common to assembly language programmers, but
> >> > even in C it's a common idiom to use an array index, this is instead a
> >> > base + offset arrangement.  Stated that way, it is easy to understand
> >> > what is going on in the code.  Not much of an intellectual burden.
> >> 
> >> I don't thinks it's a common idiom at all and I've see a lot of C over
> >> the years.  The last time I saw it was in Gregory Chaitin's tiny Lisp
> >> interpreter that he's used in his books and courses.  It's not exactly
> >> idiomatic C, but then he has bigger fish to fry.
> >
> > I take it you're refering to hiding the integer in the body of the
> > arena object for the free list via a slightly clever cast?  One of the
> > strengths of C, although it is a weakness as well since the conversion
> > of pointer types introduces complexities that can easily trip you up.
> 
> I don't think that's what I meant.  I was referring to the more dramatic
> difference: your free and allocate functions take and return ints not
> pointers.

So?  In context they are pointers.



Regards,

Uncle Steve

-- 
Should a professional politician be charged with molestation if he
kisses babies while attending political rallies?

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

#4508

On May 19, 1:20 pm, Uncle Steve <stevet...@gmail.com> wrote:
> On Thu, May 19, 2011 at 03:22:18AM +0100, Ben Bacarisse wrote:
> > Uncle Steve <stevet...@gmail.com> writes:
>
> > > On Thu, May 19, 2011 at 12:26:15AM +0100, Ben Bacarisse wrote:
> > >> Uncle Steve <stevet...@gmail.com> writes:

> > > Probably, but people with less experience might not have appreciated the
> > > simplicity of the algorithm if it was full of object padding
> > > calculations, and all the little bits that go along with it.  Of
> > > course I edited for brevity.
>
> > You edited in some bugs too:
>
> > | #define arena_obj_addr(x, n) ((void *) *(&p->arena[n * x->obj_size]))
>
> > 'p' can't be right here.  It must be 'x', yes?  The result of the
> > expression is a char converted to void *.  That can't be right either.
> > presumably the '*' in front of the '(&' should not be there.  (And I'd
> > add parentheses round all the macro arguments in the body.)
>
> You're correct.  The original function definitions have extra
> convenience macros, and the macro variables are protected from
> side-effects, etc.  Of course it should be:
>
> | #define arena_obj_addr(x, n) ((void *) *(&x->arena[n * x->obj_size]))
>
>
>
> > <snip>
> > >> (c) Other people might have to learn about the interface (and maybe
> > >> persuade themselves of the implementation) if they come to maintain code
> > >> that uses it.  Every C programmer know malloc(...).  You code, for
> > >> example, does not allocate and free using pointers -- the functions take
> > >> and return an int.  This is perfectly logical, but it will take some
> > >> getting used for the maintainer.
>
> > > Oh, absolutely.  Using integers as a sort of offset from a base is
> > > the kind of thing more common to assembly language programmers, but
> > > even in C it's a common idiom to use an array index, this is instead a
> > > base + offset arrangement.  Stated that way, it is easy to understand
> > > what is going on in the code.  Not much of an intellectual burden.
>
> > I don't thinks it's a common idiom at all and I've see a lot of C over
> > the years.  The last time I saw it was in Gregory Chaitin's tiny Lisp
> > interpreter that he's used in his books and courses.  It's not exactly
> > idiomatic C, but then he has bigger fish to fry.
>
> I take it you're refering to hiding the integer in the body of the
> arena object for the free list via a slightly clever cast?  One of the
> strengths of C, although it is a weakness as well since the conversion
> of pointer types introduces complexities that can easily trip you up.

I've been using integer offsets instead of pointers a lot lately and
I think you might be better off using the array formula explicitly:

 #define arena_obj_addr(x, n) ((void *) (x->arena + n * x->obj_size))

It's harder to get wrong.

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

#4511

On Sun, May 22, 2011 at 02:49:51AM -0700, luser- -droog wrote:
> 
> I've been using integer offsets instead of pointers a lot lately and
> I think you might be better off using the array formula explicitly:
> 
>  #define arena_obj_addr(x, n) ((void *) (x->arena + n * x->obj_size))
> 
> It's harder to get wrong.

Still, you're at the mercy of transcription errors.  Philosophically,
the arena is an array even though the program using it does not care.
But it would be better still to define the x->arena structure element
with the proper type of object so accesses would be type constrained
by the compiler and you would therefore get a warning if you tried to
assign the address to the wrong pointer.  (The following is modified
more from the real version, and less from the quick hack I posted.)

So,

#define ARENA_TYPE	struct foo


struct arena_s {
   size_t        arena_size;
   int           free_list;
   size_t        free;
   ARENA_TYPE *  arena;
};

And your access macro becomes:

#define arena_obj_addr(x, n)   &x->arena[n]

since the pointer will be of the expected type.

Even simpler.  But if your ARENA_TYPE is an odd number of bytes, this
can create alignment issues on some platforms.  On x86 there is merely
a small penalty presumably because the processor has to access two
32-bit words to resolve a structure element that crosses alignment
boundaries.  I've read that some architectures trap with a bus error
when you do this, so the easy solution is unworkable in practice
unless you carefully pad out the structure to satisfy alignment
requirements.  All I've done here is move the alignment calculations
into the arena allocator logic, looking something like this:

    op->obj_pad_size = (op->obj_size % pad_factor) ?
          (op->obj_size + pad_factor - (op->obj_size % pad_factor)) :
          op->obj_size;

And so we go back to something much more like what is in the
previously posted benchmarking code:

struct arena_s {
    size_t    obj_size;      // Size in bytes of the object
    size_t    obj_pad_size;  // Oobject size inclusive of padding
    size_t    arena_size;    // Number of obj_pad_size slots in pool
    int       free_list;     // Pointer to head of free list
    int       free;          // Number of slots remaining
    unsigned char *
              arena;         //
};

typedef struct arena_s arena;


I do in fact have a function to calculate arena_obj_addr(), and it
necessarily contains

   &p->arena[n * p->obj_pad_size]

which is of course necessary since we can't calculate obj_pad_size
before we know what the target object is and the run-time platform
constraints.  No real real reason it couldn't be "&p->arena + n *
p->obj_pad_size", but I didn't do it that way.  I guess the pointer
conversions don't cause my brain to lock-up the way they used to.



Regards,

Uncle Steve

-- 
Should a professional politician be charged with molestation if he
kisses babies while attending political rallies?

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

Page 1 of 5  [1] 2 3 4 5  Next page →

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

csiph-web