Extremly fast dinamic array implementation

[javuchi]

I just want to share some code with you, and have some comments and
improvements if you want.
This header file allocates and add and delete items of any kind of data
from a very fast array:

#include <stdlib.h>

#ifndef __LIST_H__
#define __LIST_H__

#define NEW(type) (type*)malloc(sizeof(type))

#define DEFAULT_SIZE 12

#define lNEW(type) ({ \
int *list = (int*)malloc( (sizeof(type)*DEFAULT_SIZE) \
+ (sizeof(int)*3)); \
*list++=sizeof(type); \
*list++=DEFAULT_SIZE; \
*list++=0; \
(type*)list; })

#define lSIZE(list) (*((int*)list-1))
#define lALLOCATED(list) (*((int*)list-2))
#define lOBJECTSIZE(list) (*((int*)list-3))
#define lNEWITEM(list) ({ \
if (lSIZE(list)>=lALLOCATED(list)) { \
list = (void*) ((int*)realloc((int*)list-3, \
(lSIZE(list) + DEFAULT_SIZE) * \
lOBJECTSIZE(list) + \
sizeof(int)*3) \
+ 3); \
lALLOCATED(list)+=DEFAULT_SIZE; \
} \
&list[lSIZE(list)++]; \
})

#define lAPPEND(list,obj) *lNEWITEM(list)=obj;
#define lDELITEM(list,obj) *obj=list[--lSIZE(list)]

#define lFREE(list) free((int*)list-3)

#endif



In my system, it is able to add more than 1.000.000 of items per
second, so I think it is quite fast.
And the interesting thing is that you can use the resulting array as a
normal C array, using [] to access all of its data.
Example:

typedef struct {
int onething;
char *another;
} Object;
Object *obj = lNEW(Object);
Object o = {12, "haha"};
Object *oo = lNEWITEM(obj);
lAPPEND(obj, o);
oo->another="hehe";
printf ("%i, %s", lSIZE(obj), obj[1].another);

=> prints "2, hehe"

I'm using GCC. If anyone wants to check out it using other compilers, I
will thank.

 

[pemo]

I just want to share some code with you, and have some comments and
improvements if you want.
This header file allocates and add and delete items of any kind of
data from a very fast array:

#include <stdlib.h>

#ifndef __LIST_H__
#define __LIST_H__

#define NEW(type) (type*)malloc(sizeof(type))

#define DEFAULT_SIZE 12

#define lNEW(type) ({ \
int *list = (int*)malloc( (sizeof(type)*DEFAULT_SIZE) \
+ (sizeof(int)*3)); \
*list++=sizeof(type); \
*list++=DEFAULT_SIZE; \
*list++=0; \
(type*)list; })

#define lSIZE(list) (*((int*)list-1))
#define lALLOCATED(list) (*((int*)list-2))
#define lOBJECTSIZE(list) (*((int*)list-3))
#define lNEWITEM(list) ({ \
if (lSIZE(list)>=lALLOCATED(list)) { \
list = (void*) ((int*)realloc((int*)list-3, \
(lSIZE(list) + DEFAULT_SIZE) * \
lOBJECTSIZE(list) + \
sizeof(int)*3) \
+ 3); \
lALLOCATED(list)+=DEFAULT_SIZE; \
} \
&list[lSIZE(list)++]; \
})

#define lAPPEND(list,obj) *lNEWITEM(list)=obj;
#define lDELITEM(list,obj) *obj=list[--lSIZE(list)]

#define lFREE(list) free((int*)list-3)

#endif



In my system, it is able to add more than 1.000.000 of items per
second, so I think it is quite fast.
And the interesting thing is that you can use the resulting array as a
normal C array, using [] to access all of its data.
Example:

typedef struct {
int onething;
char *another;
} Object;
Object *obj = lNEW(Object);
Object o = {12, "haha"};
Object *oo = lNEWITEM(obj);
lAPPEND(obj, o);
oo->another="hehe";
printf ("%i, %s", lSIZE(obj), obj[1].another);

=> prints "2, hehe"

I'm using GCC. If anyone wants to check out it using other compilers,
I will thank.

On my system, Object *obj = lNEW(Object); expands to ...

Object *obj = ({ int list = (int)malloc( (sizeof(Object)*12) +
(sizeof(int)*3)); *list++=sizeof(Object); *list++=12; *list++=0;
(Object*)list; });

Where should one start - the parenthesied compound statement used in the
assignment perhaps?

 

[Ancient_Hacker]

I just want to share some code with you, and have some comments and
improvements if you want.

Some comments:
(1)
It's usually a poor idea to use macros to generate substantial amounts
of code. Just one slip of the finger and the poor user will get tons
of error messages, showing tons of lines of mysterious fractured code.
How about you use some nice functions or methods?

(2) It's usually a bad sign when there's not a single error check in a
piece of complex code that can go wrong so many ways.

(3) You're schlepping off all the hard work to your particular
implementation of malloc and realloc().

otherwise okay

 

[javuchi]

Some comments:
(1)
It's usually a poor idea to use macros to generate substantial amounts
of code. Just one slip of the finger and the poor user will get tons
of error messages, showing tons of lines of mysterious fractured code.
How about you use some nice functions or methods?

I use macros because it is posible to typecast easily and
transparently, and also because they are fast. (Yes, I could use inline
functions, but still have problems managin type sizes and more.)

(2) It's usually a bad sign when there's not a single error check in a
piece of complex code that can go wrong so many ways.

Having error check is against the original intention of being fast.
With current computers, being able to allocate 4Gb or more of memory,
there is no need for such comprobations in most situations. Elsewhere,
if a program using dinamic arrays gets out of memory, the system itself
will halt down de application, so I don't agree that a memory check
would be necesary here.

(3) You're schlepping off all the hard work to your particular
implementation of malloc and realloc().

otherwise okay

Thanks for your coments.

 

[javuchi]

On my system, Object *obj = lNEW(Object); expands to ...

Object *obj = ({ int list = (int)malloc( (sizeof(Object)*12) +
(sizeof(int)*3)); *list++=sizeof(Object); *list++=12; *list++=0;
(Object*)list; });

Where should one start - the parenthesied compound statement used in the
assignment perhaps?

Bassically, what it does is to allocate a cache of objects (12 is its
size, but you can change it), and 3 more integers, which allocate each
one the size of the object, the cache size, and the actual size of the
dinamic array.
Yo can access the size of the array because it is allocated 1 point
before the address of the array. Also you access the cache size and the
size of each allocated object substracting 2 and 3 from the address of
the pointer.
In this way, you can use any object of any type and size, without
restriction and without typecast problems (as there are in GLIB, for
example).

 

[Eric Sosman]

pemo wrote:




Bassically, what it does is to allocate a cache of objects (12 is its
size, but you can change it), and 3 more integers, which allocate each
one the size of the object, the cache size, and the actual size of the
dinamic array.
Yo can access the size of the array because it is allocated 1 point
before the address of the array. Also you access the cache size and the
size of each allocated object substracting 2 and 3 from the address of
the pointer.
In this way, you can use any object of any type and size, without
restriction and without typecast problems (as there are in GLIB, for
example).

"Without restriction?" How do you handle a type whose
alignment requirement is stricter than int's? For example,
on a system with four-byte int and eight-byte double, where
double requires alignment on an eight-byte boundary, your
macro mis-aligns all the doubles.

 

[Laurent Deniau]

I just want to share some code with you, and have some comments and
improvements if you want.
This header file allocates and add and delete items of any kind of data
from a very fast array:

#include <stdlib.h>

#ifndef __LIST_H__
#define __LIST_H__

#define NEW(type) (type*)malloc(sizeof(type))

#define DEFAULT_SIZE 12

#define lNEW(type) ({ \
int *list = (int*)malloc( (sizeof(type)*DEFAULT_SIZE) \
+ (sizeof(int)*3)); \
*list++=sizeof(type); \
*list++=DEFAULT_SIZE; \
*list++=0; \
(type*)list; })

#define lSIZE(list) (*((int*)list-1))
#define lALLOCATED(list) (*((int*)list-2))
#define lOBJECTSIZE(list) (*((int*)list-3))
#define lNEWITEM(list) ({ \
if (lSIZE(list)>=lALLOCATED(list)) { \
list = (void*) ((int*)realloc((int*)list-3, \
(lSIZE(list) + DEFAULT_SIZE) * \
lOBJECTSIZE(list) + \
sizeof(int)*3) \
+ 3); \
lALLOCATED(list)+=DEFAULT_SIZE; \
} \
&list[lSIZE(list)++]; \
})

#define lAPPEND(list,obj) *lNEWITEM(list)=obj;
#define lDELITEM(list,obj) *obj=list[--lSIZE(list)]

#define lFREE(list) free((int*)list-3)

#endif

It is a strange policy, you add/remove elements only at the end, but you
allow random access? A mix between a stack and an array? (but definitely
not a list).

In my system, it is able to add more than 1.000.000 of items per
second, so I think it is quite fast.

This is not quite fast. >100.000.000 is quite fast (on a Pentium-M
1.6Ghz). The best is to compare it the speed of the C array ;-)

And the interesting thing is that you can use the resulting array as a
normal C array, using [] to access all of its data.

According to my experience, I think it is a good idea to have C-like
access for low-level very fast arrays, but it is not a good idea to mix
it with append/remove-like functions. For low-level, C-like array random
access, checked get/set and resize are a better choice. Function like
cat/append/remove start to be high level functions where the user should
not be concerned by the fact that the array pointer may change after a
cat/append, that is the array should stay the same even when its
capacity increases.

Example:

typedef struct {
int onething;
char *another;
} Object;
Object *obj = lNEW(Object);
Object o = {12, "haha"};
Object *oo = lNEWITEM(obj);
lAPPEND(obj, o);
oo->another="hehe";
printf ("%i, %s", lSIZE(obj), obj[1].another);

=> prints "2, hehe"

I'm using GCC. If anyone wants to check out it using other compilers, I
will thank.

Here is below the header of a low-level fast array interface
(implementation is an easy exercise ;-) ) which is part of my OOC
framework (required to compile, but easy to make it independent). It
allows C random access to data, it is type safe and do not use macros
(except for prefixing and some shortcuts, the later can be remove). Your
example becomes (adapted to array, not stack):

Object *obj = obj_array_new(2);
obj[0] = (Object*){12, "haha"};
obj[1] = obj[0];
obj[1].another = "hehe";
printf("%i, %s", sizeof *obj, obj[1].another);

it is easy to make a generic stack on top of this array implementation.

a+, ld.

-----------------
/* template file, multiple inclusion allowed */

/*
******************************
* Raw Array interface
* -----
* Object Oriented C programming
*
* Author: Laurent Deniau, (e-mail address removed)
*
* $Id: array_t.h,v 1.1 2004/07/04 13:52:09 ldeniau Exp $
*
* For more information, please see:
* http://cern.ch/Laurent.Deniau/html/ooc/ooc.html
*
******************************
*/

/* NOTE-USER: raw array interface

array_T : element type (e.g. int)
array_T*: array type (e.g. int*)

array_T* PREFIX_array_new (size_t cnt );
array_T* PREFIX_array_alloc (size_t cnt );
array_T* PREFIX_array_cpy (array_T *a1 , const array_T *a2);
array_T* PREFIX_array_rawcpy (array_T *a1 , const array_T *src,
size_t cnt);
array_T* PREFIX_array_dup (const array_T *a );
array_T* PREFIX_array_rawdup (const array_T *src, size_t cnt);
array_T* PREFIX_array_resize (array_T *a , size_t cnt);
array_T* PREFIX_array_realloc(array_T *a , size_t cnt);
void PREFIX_array_del (array_T *a );
void PREFIX_array_free (array_T *a );
size_t PREFIX_array_cnt (const array_T *a );
array_T PREFIX_array_get (const array_T *a, size_t idx);
void PREFIX_array_set (array_T *a, size_t idx, array_T val);
*/

#ifndef array_T
#error "libooc: missing array_T definition"
#endif

#ifndef array_PREFIX
#define array_PREFIX array_T
#endif

/*
* ----------
* Externals
* ----------
*/

void* ooc_array_new_ ( size_t cnt , size_t esize,
size_t hsize, bool ex);
void* ooc_array_resize_(void* self, size_t cnt , size_t esize,
size_t hsize, bool ex);
void* ooc_array_cpy_ (void* dst , const void* src, size_t esize,
size_t hsize);
void* ooc_array_rawcpy_(void* dst , const void* src, size_t esize,
size_t hsize, size_t cnt);
void* ooc_array_dup_ ( const void* src, size_t esize,
size_t hsize);
void* ooc_array_rawdup_( const void* src, size_t esize,
size_t hsize, size_t cnt);
void ooc_array_badrng_(const char *file, int line);

/*
* ---------------------------------------
* Array interface/inlined implementation
* ---------------------------------------
*/

#ifndef OOC_TYPE_ARRAY_C

#define T OOC_CAT(array_PREFIX, _array)
#define F(f) OOC_CAT3(T,_,f)
#define B(p) ((struct T*)((char*)(p) - offsetof(struct T, data)))

struct T {
const size_t cnt; /* read-only field */
#if OOC_ISO_C < OOC_ISO_C99
array_T data[1]; /* public field, undefined behavior, but... */
#else
array_T data[]; /* public field, defined behavior */
#endif
};

static inline array_T*
F(new) (size_t cnt)
{
return
ooc_array_new_(cnt, sizeof(array_T), offsetof(struct T, data), true);
}

static inline array_T*
F(alloc) (size_t cnt)
{
return
ooc_array_new_(cnt, sizeof(array_T), offsetof(struct T, data), false);
}

static inline array_T*
F(cpy) (array_T *dst, const array_T *src)
{
return ooc_array_cpy_((void*)dst, (void*)src,
sizeof(array_T), offsetof(struct T, data));
}

static inline array_T*
F(rawcpy) (array_T *dst, const array_T *src, size_t cnt)
{
return ooc_array_rawcpy_((void*)dst, (void*)src,
sizeof(array_T), offsetof(struct T, data), cnt);
}

static inline array_T*
F(dup) (const array_T *src)
{
return ooc_array_dup_((void*)src, sizeof(array_T),
offsetof(struct T, data));
}

static inline array_T*
F(rawdup) (const array_T *src, size_t cnt)
{
return ooc_array_rawdup_((void*)src, sizeof(array_T),
offsetof(struct T, data), cnt);
}

static inline array_T*
F(resize) (array_T *self, size_t cnt)
{
return ooc_array_resize_((void*)self, cnt,
sizeof(array_T), offsetof(struct T, data), true);
}

static inline array_T*
F(realloc) (array_T *self, size_t cnt)
{
return ooc_array_resize_((void*)self, cnt,
sizeof(array_T), offsetof(struct T, data), false);
}

static inline void
F(del) (array_T *self)
{
if (self)
(ooc_free)(B(self));
}

static inline void
F(free) (array_T *self)
{
F(del)(self);
}

static inline size_t
F(cnt) (const array_T *self)
{
return B(self)->cnt;
}

static inline array_T
F(get) (const array_T *self, size_t idx)
{
if (idx >= B(self)->cnt)
ooc_array_badrng_(__FILE__, __LINE__);

return self[idx];
}

static inline void
F(set) (array_T *self, size_t idx, array_T val)
{
if (idx >= B(self)->cnt)
ooc_array_badrng_(__FILE__, __LINE__);

self[idx] = val;
}

#undef T
#undef F
#undef B

#endif /* OOC_TYPE_ARRAY_C */

#undef array_PREFIX
#undef array_T

 

[Richard Heathfield]

(e-mail address removed) said:

I use macros because it is posible to typecast easily and
transparently,

Why on earth would you need to "typecast"? It's only an array, for pity's
sake!

and also because they are fast.

Macros don't have a speed. They are completely replaced by the time the
preprocessing is done.

I suggest you take a careful note of the following diagnostic messages which
gcc produces:

foo.c:46: warning: ANSI C forbids braced-groups within expressions
foo.c:47: warning: initialization discards qualifiers from pointer target
type
foo.c:48: warning: ANSI C forbids braced-groups within expressions
foo.c:49: warning: ANSI C forbids braced-groups within expressions
foo.c:50: warning: assignment discards qualifiers from pointer target type

Having error check is against the original intention of being fast.

In which case you can make it a lot faster like this:

int main(void)
{
return 0;
}

If it doesn't have to get the answer right, it can be very quick indeed.

With current computers, being able to allocate 4Gb or more of memory,
there is no need for such comprobations in most situations.

And if every program on your computer assumes it can get 4GB?

Elsewhere,
if a program using dinamic arrays gets out of memory, the system itself
will halt down de application,

Your users might appreciate it if the program at least /tried/ to save their
data for them before halting.

so I don't agree that a memory check
would be necesary here.

I don't agree that your code would be necessary here.

 

[Richard Heathfield]

(e-mail address removed) said:

Bassically, what it does is to allocate a cache of objects

You misunderstand; pemo is saying that the code is not legal C. And he's
right.

 

[Flash Gordon]

Bassically, what it does is to allocate a cache of objects (12 is its

<snip>

No it doesn't. It causes the compiler to emit a diagnostic. On many
systems the diagnostic is an error message and no program is produced.
Basically, ({}) is a GNU extension and *not* standard C, it is also not
implemented on a lot of other compilers. In addition, we talk about C
here, not the GNU extensions to C.

 

[websnarf]

I just want to share some code with you, and have some comments and
improvements if you want.
This header file allocates and add and delete items of any kind of data
from a very fast array:

#include <stdlib.h>

#ifndef __LIST_H__
#define __LIST_H__

#define NEW(type) (type*)malloc(sizeof(type))

#define DEFAULT_SIZE 12

#define lNEW(type) ({ \
int *list = (int*)malloc( (sizeof(type)*DEFAULT_SIZE) \
+ (sizeof(int)*3)); \
*list++=sizeof(type); \
*list++=DEFAULT_SIZE; \
*list++=0; \
(type*)list; })

#define lSIZE(list) (*((int*)list-1))
#define lALLOCATED(list) (*((int*)list-2))
#define lOBJECTSIZE(list) (*((int*)list-3))
#define lNEWITEM(list) ({ \
if (lSIZE(list)>=lALLOCATED(list)) { \
list = (void*) ((int*)realloc((int*)list-3, \
(lSIZE(list) + DEFAULT_SIZE) * \
lOBJECTSIZE(list) + \
sizeof(int)*3) \
+ 3); \
lALLOCATED(list)+=DEFAULT_SIZE; \
} \
&list[lSIZE(list)++]; \
})

#define lAPPEND(list,obj) *lNEWITEM(list)=obj;
#define lDELITEM(list,obj) *obj=list[--lSIZE(list)]

#define lFREE(list) free((int*)list-3)

#endif

1) You don't have a "get item" macro. Using lAPPEND and lDELETE you
can only use this like a stack. If that is your intent then you
should call it a stack.

2) You are using linear reallocs instead of exponential reallocs. This
makes things slow.

3) You are stuffing size_t integers into int spaces. This will not be
correct on 16 or 64 bit systems. So you should use size_t *, instead
of int * for those entries.

In my system, it is able to add more than 1.000.000 of items per
second, so I think it is quite fast.

On a 1Ghz machine, that's 1000 clocks for a single add. That's not
very fast at all. For something like this I am would be expecting
something like 5 to 10 clocks.

Personally, I would try to make a design using the struct hack, to get
some semblance of type safety:

struct list {
size_t objsize, alloc, len;
void entries[1];
};

and you can use the offsetof() macro from stddef, if you really want
the handle to be pointing at the array part of the list. And for "add
item" or whatever, you should *double* the allocated size, not simply
add one entry to it. In this way, you have a guarantee that the number
of calls to realloc (which is really really slow, BTW) is in fact
bounded above by a fairly small reasonable number (usually 16, 32 or 64
depending on the addressable space on your machine).

You are also paying a penalty for making your list so type generic.
You have to store an extra object size value around, even though this
size will usually be constant with respect to each usage/line of code.
If you are more type specific, then this size becomes implicitly
available at compile time. That would save an entry and avoid problems
with mixing up of different lists accidentally.

Being type specific, it would also help you be able to add an "append
list" operation. I.e,. you can take two lists and add one to the
other. This would ordinarily be extremely dangerous unless you had
type checking.

And the interesting thing is that you can use the resulting array as a
normal C array, using [] to access all of its data.

I.e., its a buffer overflow waiting to happen.