Boost-Commit :

Date view	Thread view	Subject view	Author view

Subject: [Boost-commit] svn:boost r53966 - in sandbox/monotonic/libs/monotonic: doc test
From: christian.schladetsch_at_[hidden]
Date: 2009-06-16 01:04:58

Next message: christian.schladetsch_at_[hidden]: "[Boost-commit] svn:boost r53967 - sandbox/monotonic/libs/monotonic/doc"
Previous message: christian.schladetsch_at_[hidden]: "[Boost-commit] svn:boost r53965 - sandbox/monotonic/boost/monotonic"

Author: cschladetsch
Date: 2009-06-16 01:04:57 EDT (Tue, 16 Jun 2009)
New Revision: 53966
URL: http://svn.boost.org/trac/boost/changeset/53966

Log:
update to dox, VS will prolly corrupt it all

Text files modified:
   sandbox/monotonic/libs/monotonic/doc/index.html | 145 +++++++++++++++++++--------------------
   sandbox/monotonic/libs/monotonic/test/monotonic.vcproj | 8 ++
   2 files changed, 80 insertions(+), 73 deletions(-)

Modified: sandbox/monotonic/libs/monotonic/doc/index.html
==============================================================================
--- sandbox/monotonic/libs/monotonic/doc/index.html (original)
+++ sandbox/monotonic/libs/monotonic/doc/index.html 2009-06-16 01:04:57 EDT (Tue, 16 Jun 2009)
@@ -24,7 +24,7 @@
 <th class="docinfo-name">
 Version:</th>
 <td>
- 0.1a</td>
+ 0.2a</td>
 </tr>
 <tr class="field">
 <th class="docinfo-name">
@@ -38,9 +38,10 @@
 <h1>
 Boost.Monotonic</h1>
 
- This proposal uses std::allocators and a common storage concept to provide
- correctly-aligned allocation of objects of different types from the same buffer.
- This buffer can be on the heap or on the stack. The allocation model is designed
+ This proposal uses a custom allocator and a common storage concept to provide
+ allocation of objects of different types from the same buffer.
+ This buffer can be on the stack, on the heap, or spanning both the stack and the
+ heap. The allocation model is designed
 to be optimal in time with also zero space overhead per allocation made.
 
 The name 'monotonic' has been criticised as being too general and not really
@@ -50,7 +51,7 @@
 Motivation
 </h2>
 
- We would sometimes like to use the various STL containers and use the stack for
+ We would sometimes like for containers to use the stack for
 their storage. In
 this way, for example, a map<K, list< vector<T> > > can use storage from the stack
 for the map, the list and the vector, rather than
@@ -59,7 +60,9 @@
 Also, it would be great if the same storage
 could be used by different containers, and even better if we could choose to use
 the stack or the heap, and better still if there was zero overhead for the
- memory allocations.
+ memory allocations. Of course, we would like the storage to use the heap after 
+ the reserved stack-space is exhausted, and it has to be optionally thread-safe
+ as well.
 
 There are many uses for such a system, including very fast and very small data
 structures, per-frame containers,
@@ -68,7 +71,7 @@
 
 This is what this library does, by collaborating multiple instances of
 monotonic::allocator<T> with a
- common montonic::storage<N>.
+ common montonic::storage<>.
 It is a fast allocation system, O(1) to allocate and zero-cost to deallocate; hence the proposed name of a
 "monotonic" allocator. 
 <h2 id="Proposal">
@@ -80,9 +83,8 @@
 simplifies the syntax somewhat.
 <pre>void shared() {
 // declare the storage that will be shared by the various containers.
- // storage is on the stack here, but can be put on the heap with `new`
- boost::monotonic::inline_storage<10000> storage; {
- std::map<int, int, std::less<int>, boost::monotonic::allocator<int> > map(storage);
+ // storage will use the stack at first, then transparently expand to the heap as needed
+ boost::monotonic::storage<> storage; { std::map<int, int, std::less<int>, boost::monotonic::allocator<int> > map(storage);
 map[1] = 2;
 map[2] = 4;

@@ -107,73 +109,69 @@
 system with the following
 properties: 
 <ul>
- <li>Space for objects is pre-allocated. This can be on the heap or
- on the stack. </li>
- <li>Objects are initialised only as required. </li>
- <li>De-allocating an object calls its destructor iff it has one.</li>
+ <li>SSpace for objects is pre-allocated. This can be on the stack, on the heap, or
+ spanning both. </li>
+ <li>Objects are initialised only as required. /li>
+ <li>DDe-allocating an object does nothing other than call its destructor iff it has one.</li>
 <li>Object storage is not reclaimed until the underlying storage goes out of scope.
 </li>
 <li>Multiple different containers of any type can share the same storage via
 different allocators.</li>
+ <li>Containers on the stack are thread-safe by default.</li>
+ <li>monotonic::shared_storage can be used otherwise for multi-threaded applications.</li>
 </ul>
 
 The benefits of using a monotonic::allocator over other allocators are:
- <ul>
+ ul>
 <li>All storage is pre-allocated, similar to a pool </li>
 <li>Storage can be on the stack: <ul>
 <li>Heap is not even used, let alone fragmented </li>
- <li>Cache coherency is high </li>
+ <li>CCache coherency is high </li>
 </ul>
 </li>
+ <li>Allocations will first exhaust any reserved space on the stack before reverting
+ to the heap. This is transparent to users of the allocator, such as containers.</li>
 <li>Allocation is lightening-fast as it only involves advancing a pointer and
 possible alignment.</li>
 <li>Deallocation is even faster as it does absolutely nothing </li>
- <li>Different containers can share the same storage </li>
+ <li>Different containers can share the same storage /li>
 </ul>
 
- There are also limitations: 
+ There are alsThere are also limitations: 
 <ul>
 <li>Containers must be constructed with either an allocator or storage. There are no
 default allocators, and hence no default container constructors. </li>
 <li>Storage grows monotonically: removing objects from a container does not
 de-allocate memory </li>
- <li>Stackspace is limited and putting large containers on the stack may exhaust
- stack space
- <ul>
- <li>This can be addressed on a per-compiler basis </li>
- <li>The system can be used with the storage on the heap </li>
- </ul>
- </li>
- </ul>
- 
- TODO:
- 
- <ul>
- <li>provide details on default stack-sizes on each target platform </li>
- <li>provide details as details on how to increase this. </li>
- <lprovide guidance on 'good' sizes for containers that are stored on the stack
- </li>
 </ul>
 <h2 id="Architecture">
 Architecture
 </h2>
 
 The architecture is quite simple. There are three main components: the storage,
- the allocator and the container. The storage is based on boost::array<char,N>
- and is on the stack or the heap. The allocator is stored in the container, which
+ the allocator and the container. FixedStorage is based on boost::array<char,N>
+ and is on the stack or the heap. Storage has-a FixedStorage, and a chain of
+ larger memory buffers on the heap that are created as needed. The allocator is stored in the container, which
 is initialised with either an allocator or storage.<h3 id="Containers">
+ Fixed
 Storage</h3>
 
 The storage is provided via boost::monotonic::storage<size_t num_bytes>
 
 Put it on the stack to use storage on the stack, or put it on the heap to use
 storage on the heap.
+ <h3 id="Containers0">
+ Storage</h3>
+ 
+ Storage has a FixedStorage component, and a collection of memory buffers called
+ a chain. To service an incoming allocation request, the Storage first attempts
+ to allocate from its FixedStorage. If that fails, it uses space from the first
+ suitable buffer in the chain.
 <h3>
 Allocator</h3>
 
 boost::monotonic::allocator<T> provides a means for a set of containers to share
- monotonic::storage.
- 
+ monotonic::storage. 
 Allocations performed
 by this allocator are correctly aligned for each container independantly (thanks
 Artyom, Thorsten!); de-allocations
@@ -186,12 +184,10 @@
 Containers
 </h3>
 
- The following container wrappers are, currently and precipitously, part of this proposal: 
+ The followingThe following container wrappers are, currently and precipitously, part of this proposal: 
 <ul>
- <li>bboost::monotonic::list<T></li>
- <li>boost::monotonic::vector<T> /li>
- <li>boost::monotonic::map<K,T> </li>
- <li>boost::monotonic::multi_map<K,T> </li>
+ <li>boost::monotonic::list<T></li>
+ <li>boost::monotonic::vector<T><li>boost::monotonic::map<K,T> <li>boost::monotonic::multi_map<K,T> </li>
 <li>boost::monotonic::set<T> </li>
 <li>boost::monotonic::multi_set<T> </li>
 <li>boost::monotonic::ptr_list<T> </li>
@@ -217,41 +213,47 @@
 <h2 id="ExampleUsage">
 Memory Fragmentation</h2>
 
- The proposed system can be used to reduce memory fragmentation, or remove it
+ The proposed The proposed system can be used to reduce memory fragmentation, or remove it
 completely. For example:
 <pre>void Mainloop()()
{
- boost::monotonic::storage<100000> storage;
+ boost::monotonic::storage<> storage;
 for (;;)
 {
 DoStuff(storage);
 storage.reset();
 }
}</pre>
+ <h2 id="ExampleUsage0">
+ Thread Safety</h2>
+ 
+ Containers that are on the stack are thread-safe by default.
+ 
+ Use boost::monotonic::shared_storage<> for multi-threaded applications
+ otherwise.
 <h2>
 Performance</h2>
 
 This is still under investigation. Results to follow. The code in the sandbox
- gives a favorable indication, but far more exhaustive testing is required before
+ provides a favorable indication, but far more exhaustive testing is required before
 any claims can be confidently made.
 <h2>
 Example Usage
- </h2>
- 
+ 
 Quite often, we need to create a temporary collection of objects which will
 exist only for the duration of a code block. A common pattern for this is to
 collect a set of objects from a container to do some work on: 
 <div class="code">
 <pre>void MainLoop()
{
- boost::monotonic::inline_storage<100*sizeof(Object)> storage; // create local storage on the stack
- boost::monotonic::list<Object> deathrow(storage); > storage; // create local storage on the stack. default to 8k, will move to heap as required
+ std::list<Object, boost::monotonic::allocator<Object> > deathrow(storage); // create a std::list that uses this storage</pre>
 <pre> foreach (object in world)
 {
- if (IsDead(object))
+ ifIsDead(object))
 deathrow.push_back(object); // allocation is just advancing a pointer
 }
 foreach (object in deathrow)
@@ -259,10 +261,8 @@
 world.Remove(object);
 object.Delete();
 }
- // storage is removed from stack; the heap is not touched
-}
-</pre>
- </div>
+ // storage is// storage is freed
+} </div>
 
 The same system can be used to store very large containers on the heap but still
 using a monotonic allocator:
@@ -274,14 +274,13 @@
 std::auto_ptr<boost::monotonic::storage<1000*1000*1000> > storage = new boost::monotonic::storage<1000*1000*1000>();

- // create a hash-table-based mapping of ints to ints using a monotonic allocator
- boost::monotonic::unsorted_map<int, int> table(*storage);
+ // create a h// create a large mapping of ints to ints using a monotonic allocator
+ std::map<int, int, std::less<int>, monotonic::allocator<int> table(*storage);

 // populate the container; no new heap allocations are performed
 for (int n = 0; n < 1000*1000; ++n)
 {
- // storage created for the hash-table (including the lists) is pre-allocated
+ // storage created for the table (including the lists) is pre-allocated
 // and each allocation requires only a pointer advance
 table[rand()] = n;
 }
@@ -298,25 +297,25 @@
 <div class="code">
 <pre>void DoSomething(boost::monotonic::storage_base &storage)
{
- boost::monotonic::list<Object> vector(storage);
+ std::list<Object, boost::monotonic::allocator<Object> > list(storage);
 // populate and use vector
 DoSomethingElse(storage);
}

void DoSDoSomethingElse(boost::monotonic::storage_base &storage)
{
- boost::monotonic::map<int, Object> map(storage);
+ std::map<int, Object, std::less<int>, boost::monotonic::allocator<int> > map(storage);
 // populate and use map
}

void MainLoop()
{
- while (!Finished())
- {
- boost::monotonic::inline_storage<10*1000> storage;
- DoSomething(storage);
- // storage is released, ready for next loop
- }
+ boost::monotonic::storage<> storage;
+ while (!Finished())
+ {
+ DoSomething(storage);
+ storage.reset(); // set the number of bytes used to zero
+ }
}
</pre>
 </div>
@@ -328,13 +327,13 @@
 <div class="code">
 <pre>void Object::Recurse()
{
- boost::monotonic::inline_storage<5000> storage; // create storage on the stack for a set
- Recurse(boost::monotonic::set<int>(storage)); storage; // create storage on the stack for a set
+ Recurse(std::set<int, std::less<int>, boost::monotonic::allocator<int> >(storage)); // recurse, passing the set
}

-void Object::Recurse(boost::monotonic::set<int> &set)
+void Object::Recurse(std::set<int, std::less<int>, boost::monotonic::allocator<int> > &set)
{
 if (set.find(handle) != set.end()) return; // avoid infinite recursion
@@ -360,7 +359,7 @@
 allocator as well.
 <h2>
 References</h2>
- <li>Boost.AlignedMemory</li>
+ <li>Boost.AlignedStorage</li>
 <li>Boost.AutoBuffer. A related service. Attempts to integrate this with STL has so
 far been unsuccessful. See libs/monotonic/test/main.cpp#test_auto_buffer</li>
 <li>Boost.IntrusiveContainer, for an alternative means of creating efficient

Modified: sandbox/monotonic/libs/monotonic/test/monotonic.vcproj
==============================================================================
--- sandbox/monotonic/libs/monotonic/test/monotonic.vcproj (original)
+++ sandbox/monotonic/libs/monotonic/test/monotonic.vcproj 2009-06-16 01:04:57 EDT (Tue, 16 Jun 2009)
@@ -355,6 +355,14 @@
 RelativePath=".\test_shared_storage.cpp"
>
 <FileConfiguration
+ Name="Debug|Win32"
+ ExcludedFromBuild="true"
+ >
+ <Tool
+ Name="VCCLCompilerTool"
+ />
+ </FileConfiguration>
+ <FileConfiguration
 Name="Release|Win32"
 ExcludedFromBuild="true"
>

Next message: christian.schladetsch_at_[hidden]: "[Boost-commit] svn:boost r53967 - sandbox/monotonic/libs/monotonic/doc"
Previous message: christian.schladetsch_at_[hidden]: "[Boost-commit] svn:boost r53965 - sandbox/monotonic/boost/monotonic"

Date view	Thread view	Subject view	Author view

Boost-Commit list run by bdawes at acm.org, david.abrahams at rcn.com, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk