Synopsis: Recycle lists in C++. April 98 From erwin@pip.dknet.dk Sun Apr 19 10:05:42 1998 Date: Sun, 19 Apr 1998 10:05:37 +0200 (MET DST) From: "Erwin S. Andreasen" X-Sender: erwin@shire.shire.dk Reply-To: erwin@pip.dknet.dk To: mkw cc: "rom@rom.org" Subject: Re: C++ and ROM's internal memory recycling system On Sat, 18 Apr 1998, mkw wrote: > Erwin, I believe you said at some point that you also use C++ to expand ROM. Do > you compile the entire MUD as C++, or just part of it? > > I am currently still compiling the core functions as C, mostly due to the fact > that the memory recycling system isn't compatible with ANSI C++ (illegal to cast > (void*) to (char*).) > > I wonder what effect on runtime performance it would have to throw out the whole > internal memory managment system and just use operator new instead. > > Does anyone have any practical experience regarding this issue? Indeed, the whole (Envy, not ROM) MUD compiles as C++. It would be slower: for most structures, all MERC derivatives keep a freelist of previously freed structures, so allocating one when there is one free is a matter of 2-3 pointer instructions. How much this exactly translates to is hard to say, but probably very little, unfortunately I have no recent profiling information around. It would also take up more space: most structures are allocated using alloc_perm in MERC, which wastes very little memory since it saves no information about the size of memory. If we assume new will use power-of-2 for allocation, a say, 180 byte char_data will waste 76 bytes, plus perhaps 4 bytes more for other overhead, for a total of 80 bytes, which is 44%. Most malloc implementations might be better however, and perhaps be able to allocate chunks of say, 4 bytes, 8 bytes, 16 bytes, 20 bytes etc. Then you'll waste perhaps 16-20 bytes - but it'll be slower. However, it is entirely possible to implement a freelist scheme fairly automatically. Take a look at SAM (http://www.abandoned.org/nemon/) - we have since converted this to C++. Roughtly how it works in C++ (check the C code first!): // Here is a Character struct Character : public Entity { public: // The standard allocator is used: ALLOCATOR(Character); [...] }; // The allocator maro defines this: a new and delete operator that // call theCharacter_allocator.allocate and free #define ALLOCATOR(type) \ ~type(); \ void* operator new(size_t _size, type *at=NULL) { return at ? (void *)at : type##_allocator.allocate(); } \ void operator delete(void *ptr) { type##_allocator.deallocate((type*)ptr); } // theCharacter_allocator is a template class, parameterized with // Character. It looks roughly like this: template class Allocator { private: T *freelist; // List of freed Ts T *prelist; // List of Ts that were allocated in one big chunk int freecount; /* on free list */ int precount; /* on preallocated list */ int count; /* In use */ int prealloc_start;/* How many ordered preallocated initially */ int size; // sizeof(T) T *prestart, *preend; /* first, last+1 preallocated pointer */ public: Allocator(); T* allocate (); void deallocate (T *ptr); int getPreallocStartCount() const { return prealloc_start; } int getFreeCount() const { return freecount; } int getPreallocCount() const { return precount; } int getCount() const { return count; } void preallocate(int n); void printStats (Buffer& buffer, const char *name) const; void setSize(int s) { size = s; } }; The allocators are defined automagically based on some macros (again, check the current C version of SAM): the file h/alloc-list.h contains lines like this: ALLOC(Character, "characters", 6500) Allocate structures of type "Character", call them "characters" on statistics, and allocate 6500 of them in one huge chunk (with no overhead!) on startup. This macro is then used to declare and define theCharacter_allocator, as well as to call the preallocate method for all those allocators. This preallocate method allocates 6500 Characters in one huge chunk of memory, saving quite a lot of overhead, and hands them out one by one as the MUD asks for them. The macro is used also to make automatic output of 'memory' command: Structure |Size |In use |Prealloc |Freelist | | |count bytes|count bytes|count bytes| accounts | 148| 24 3552| N/A | 1 148| account characters | 44| 93 4092| N/A | 5 220| affects | 20| 4411 88220| 0 0| 188 3760| aliases | 12| 109 1308| N/A | 117 1404| auction objects | 52| 105 5460| N/A | 0 0| arena bets | 16| 0 0| N/A | 0 0| bounties | 40| 27 1080| N/A | 0 0| areas | 172| 102 17544| N/A | 0 0| bans | 28| 25 700| N/A | 0 0| blacklists | 8| 557 4456| N/A | 0 0| CL heads | 40| 79 3160| N/A | 0 0| CL nodes | 12| 987 11844| N/A | 0 0| characters | 320| 6628 2120960| 6 1920| 28 8960| [...] ============================================================================== Erwin Andreasen Herlev, Denmark UNIX System Programmer <*> (not speaking for) DDE ==============================================================================