This is the mail archive of the
libstdc++@gcc.gnu.org
mailing list for the libstdc++ project.
Patch mt_allocator
- From: Stefan Olsson <stefan at xapa dot se>
- To: Benjamin Kosnik <bkoz at redhat dot com>
- Cc: libstdc++ <libstdc++ at gcc dot gnu dot org>, Felix Yen <fwy at alumni dot brown dot edu>
- Date: Fri, 13 Feb 2004 15:52:16 +0100
- Subject: Patch mt_allocator
Hi,
here's a patch (both source and doc) that removes the last pointers
completely (as proposed by Felix Yen) which further improves MT
performance by roughly 10%!
Brgds
/Stefan
2004-02-13 Stefan Olsson <stefan@xapa.se>
* include/ext/mt_allocator.h: Removed the last pointer. Deallocated blocks
are now added to the front of freelists as proposed by Felix Yen.
This gives roughly 10% performance boost and saves some memory.
* docs/html/ext/mt_allocator.html: Change due to that deallocated blocks now
are added to the front of freelists. The reason to this approach is
also explained.
*** mt_allocator.h Fri Feb 13 14:57:58 2004
--- mt_allocator.h.last Fri Feb 13 15:24:07 2004
*************** namespace __gnu_cxx
*** 197,208 ****
struct bin_record
{
/*
! * An "array" of pointers to the first/last free block for each
! * thread id. Memory to these "arrays" is allocated in _S_init()
* for _S_max_threads + global pool 0.
*/
block_record** volatile first;
- block_record** volatile last;
/*
* An "array" of counters used to keep track of the amount of blocks
--- 197,207 ----
struct bin_record
{
/*
! * An "array" of pointers to the first free block for each
! * thread id. Memory to this "array" is allocated in _S_init()
* for _S_max_threads + global pool 0.
*/
block_record** volatile first;
/*
* An "array" of counters used to keep track of the amount of blocks
*************** namespace __gnu_cxx
*** 336,370 ****
block->next = NULL;
block->thread_id = thread_id;
- _S_bin[bin].last[thread_id] = block;
}
else
{
size_t global_count = 0;
while( _S_bin[bin].first[0] != NULL &&
global_count < block_count )
{
block = _S_bin[bin].first[0];
if (_S_bin[bin].first[thread_id] == NULL)
! _S_bin[bin].first[thread_id] = block;
else
! _S_bin[bin].last[thread_id]->next = block;
!
! _S_bin[bin].last[thread_id] = block;
block->thread_id = thread_id;
_S_bin[bin].free[thread_id]++;
! _S_bin[bin].first[0] = _S_bin[bin].first[0]->next;
global_count++;
}
- block->next = NULL;
-
__gthread_mutex_unlock(_S_bin[bin].mutex);
}
--- 335,374 ----
block->next = NULL;
block->thread_id = thread_id;
}
else
{
size_t global_count = 0;
+ block_record* tmp;
+
while( _S_bin[bin].first[0] != NULL &&
global_count < block_count )
{
+ tmp = _S_bin[bin].first[0]->next;
+
block = _S_bin[bin].first[0];
if (_S_bin[bin].first[thread_id] == NULL)
! {
! _S_bin[bin].first[thread_id] = block;
! block->next = NULL;
! }
else
! {
! block->next = _S_bin[bin].first[thread_id];
! _S_bin[bin].first[thread_id] = block;
! }
block->thread_id = thread_id;
_S_bin[bin].free[thread_id]++;
! _S_bin[bin].first[0] = tmp;
global_count++;
}
__gthread_mutex_unlock(_S_bin[bin].mutex);
}
*************** namespace __gnu_cxx
*** 404,410 ****
}
block->next = NULL;
- _S_bin[bin].last[0] = block;
block = _S_bin[bin].first[0];
--- 408,413 ----
*************** namespace __gnu_cxx
*** 464,475 ****
block_record* block = (block_record*)((char*)__p
- sizeof(block_record));
- /*
- * This block will always be at the back of a list and thus
- * we set its next pointer to NULL.
- */
- block->next = NULL;
-
#ifdef __GTHREADS
if (__gthread_active_p())
{
--- 467,472 ----
*************** namespace __gnu_cxx
*** 491,515 ****
{
__gthread_mutex_lock(_S_bin[bin].mutex);
while (remove > 0)
{
if (_S_bin[bin].first[0] == NULL)
! _S_bin[bin].first[0] = _S_bin[bin].first[thread_id];
else
! _S_bin[bin].last[0]->next = _S_bin[bin].first[thread_id];
!
! _S_bin[bin].last[0] = _S_bin[bin].first[thread_id];
! _S_bin[bin].first[thread_id] =
! _S_bin[bin].first[thread_id]->next;
_S_bin[bin].free[thread_id]--;
remove--;
}
- _S_bin[bin].last[0]->next = NULL;
-
__gthread_mutex_unlock(_S_bin[bin].mutex);
}
--- 488,517 ----
{
__gthread_mutex_lock(_S_bin[bin].mutex);
+ block_record* tmp;
+
while (remove > 0)
{
+ tmp = _S_bin[bin].first[thread_id]->next;
+
if (_S_bin[bin].first[0] == NULL)
! {
! _S_bin[bin].first[0] = _S_bin[bin].first[thread_id];
! _S_bin[bin].first[0]->next = NULL;
! }
else
! {
! _S_bin[bin].first[thread_id]->next = _S_bin[bin].first[0];
! _S_bin[bin].first[0] = _S_bin[bin].first[thread_id];
! }
! _S_bin[bin].first[thread_id] = tmp;
_S_bin[bin].free[thread_id]--;
remove--;
}
__gthread_mutex_unlock(_S_bin[bin].mutex);
}
*************** namespace __gnu_cxx
*** 518,528 ****
* counters and owner id as needed
*/
if (_S_bin[bin].first[thread_id] == NULL)
! _S_bin[bin].first[thread_id] = block;
else
! _S_bin[bin].last[thread_id]->next = block;
!
! _S_bin[bin].last[thread_id] = block;
_S_bin[bin].free[thread_id]++;
--- 520,534 ----
* counters and owner id as needed
*/
if (_S_bin[bin].first[thread_id] == NULL)
! {
! _S_bin[bin].first[thread_id] = block;
! block->next = NULL;
! }
else
! {
! block->next = _S_bin[bin].first[thread_id];
! _S_bin[bin].first[thread_id] = block;
! }
_S_bin[bin].free[thread_id]++;
*************** namespace __gnu_cxx
*** 541,551 ****
* Single threaded application - return to global pool
*/
if (_S_bin[bin].first[0] == NULL)
! _S_bin[bin].first[0] = block;
else
! _S_bin[bin].last[0]->next = block;
!
! _S_bin[bin].last[0] = block;
}
}
};
--- 547,561 ----
* Single threaded application - return to global pool
*/
if (_S_bin[bin].first[0] == NULL)
! {
! _S_bin[bin].first[0] = block;
! block->next = NULL;
! }
else
! {
! block->next = _S_bin[bin].first[0];
! _S_bin[bin].first[0] = block;
! }
}
}
};
*************** namespace __gnu_cxx
*** 669,680 ****
if (!_S_bin[bin].first)
std::__throw_bad_alloc();
- _S_bin[bin].last = static_cast<block_record**>(::operator
- new(sizeof(block_record*) * __n));
-
- if (!_S_bin[bin].last)
- std::__throw_bad_alloc();
-
#ifdef __GTHREADS
if (__gthread_active_p())
{
--- 679,684 ----
*************** namespace __gnu_cxx
*** 708,714 ****
for (size_t thread = 0; thread < __n; thread++)
{
_S_bin[bin].first[thread] = NULL;
- _S_bin[bin].last[thread] = NULL;
#ifdef __GTHREADS
if (__gthread_active_p())
{
--- 712,717 ----
*** mt_allocator.html.orig Fri Feb 13 15:30:09 2004
--- mt_allocator.html Fri Feb 13 15:45:56 2004
*************** The _S_init() function:
*** 107,114 ****
This holds the pointer to the first free block for each thread in this
bin. I.e., if we would like to know where the first free block of size 32
for thread number 3 is we would look this up by: _S_bin[ 5 ].first[ 3 ]
- - bin_record->last = See above, the only difference being that this points
- to the last record on the same freelist.
The above created block_record pointers members are now initialized to
their initial values. I.e. _S_bin[ n ].first[ n ] = NULL;
--- 107,112 ----
*************** This is the first two blocks in freelist
*** 196,204 ****
| | |
+----------------+ |
+----------------+ |
! | next* |<-+ (If next == NULL it's the last one on the list and
! | | then the _S_bin[ 3 ].last[ 3 ] pointer points to
! | | here as well)
| |
+----------------+
| thread_id = 3 |
--- 194,202 ----
| | |
+----------------+ |
+----------------+ |
! | next* |<-+ (If next == NULL it's the last one on the list)
! | |
! | |
| |
+----------------+
| thread_id = 3 |
*************** If the freelist is empty (the pointer is
*** 242,257 ****
system and build us a freelist within this memory. All requests for new memory
is made in chunks of _S_chunk_size. Knowing the size of a block_record and
the bytes that this bin stores we then calculate how many blocks we can create
! within this chunk, build the list, remove the first block, update the pointers
! (_S_bin[ bin ].first[ 0 ] and _S_bin[ bin ].last[ 0 ]) and return a pointer
! to that blocks data.
</p>
<p>
Deallocation is equally simple; the pointer is casted back to a block_record
! pointer, lookup which bin to use based on the size, add the block to the end
! of the global freelist (with the next pointer set to NULL) and update the
! pointers as needed (_S_bin[ bin ].first[ 0 ] and _S_bin[ bin ].last[ 0 ]).
</p>
<h3 class="left">
--- 240,260 ----
system and build us a freelist within this memory. All requests for new memory
is made in chunks of _S_chunk_size. Knowing the size of a block_record and
the bytes that this bin stores we then calculate how many blocks we can create
! within this chunk, build the list, remove the first block, update the pointer
! (_S_bin[ bin ].first[ 0 ]) and return a pointer to that blocks data.
</p>
<p>
Deallocation is equally simple; the pointer is casted back to a block_record
! pointer, lookup which bin to use based on the size, add the block to the front
! of the global freelist and update the pointer as needed
! (_S_bin[ bin ].first[ 0 ]).
! </p>
!
! <p>
! The decision to add deallocated blocks to the front of the freelist was made
! after a set of performance measurements that showed that this is roughly 10%
! faster than maintaining a set of "last pointers" as well.
</p>
<h3 class="left">
*************** current threads freelist instead of to t
*** 350,356 ****
<p>
The basic process of a deallocation call is simple: always add the
! block to the end of the current threads freelist and update the
counters and pointers (as described earlier with the specific check of
ownership that causes the used counter of the thread that originally
allocated the block to be decreased instead of the current threads
--- 353,359 ----
<p>
The basic process of a deallocation call is simple: always add the
! block to the front of the current threads freelist and update the
counters and pointers (as described earlier with the specific check of
ownership that causes the used counter of the thread that originally
allocated the block to be decreased instead of the current threads