...and this line of analysis brings us deep into the ''Buffer Provider''
concept developed in 2012 — which appears to be very well to the point
and stands the test of time.
Adding some ''variadic arguments'' at the right place surprisingly leads
to an ''extension point'' — which in turn directly taps into the
still quite uncharted territory interfacing to a **Domain Ontology**;
the latter is assumed to define how to deal with entities and relationships
defined by some media handling library like e.g. FFmpeg.
So what we're set to do here is actually ''ontology mapping....''
The immediate next step is to build some render nodes directly
in a test setting, without using any kind of ''node factory.''
Getting ahead with this task requires to identify the constituents
to be represented on the first code layer for the reworked code
(here ''first layer'' means any part that are ''not'' supplied
by generic, templated building blocks).
Notably we need to build a descriptor for the `FeedManifold` —
which in turn implies we have to decide on some fundamental aspects
of handling buffers in the render process.
To allow rework of the `ProcNode` connectivity, a lot of presumably obsoleted
draft code from 2011 has to be detached, to be able to keep it in-tree
for further reference (until the rework and refactoring is settled).
As outlined in #1367, the integration effort requires some rework
of existing code, which will be driven ahead by the `NodeLinkage_test`
* redefine Node Connectivity
* build simple `ProcNode` directly in scope
* create an `TurnoutSystem` instance
* perform a ''dummy Node-Invocation''
As a replacement for the `RefArray` a new generic container
has been implemented and tested, in interplay with `AllocationCluster`
* the front-end container `lib::Several<I>` exposes only a reference
to the ''interface type'' `I`, while hiding any storage details
* data can only be populated through the `lib::SeveralBuilder`
* a lot of flexibility is allowed for the actual element data types
* element storage is maintained in a storage extent, managed through
a custom allocator (defaulting to `std::allocator` ⟹ heap storage)
The `SeveralBuilder` employs the same tactic as `std::vector`,
by over-allocating a reserve buffer, which grows in exponential
increments, to amortise better the costs of re-allocation.
This tactic does not play well with space limited allocators
like `AllocationCluster` however; it is thus necessary to provide
an extension point where the actuall allocator's limitation can be
queried, allowing to use what is available as reserve, but not more.
With these adaptations, a full usage cycle backed by `AllocationCluster`
can be demonstrated, including variations of dynamic allocation adjustment.
...identified as part of bug investigation
* make clear that reserve() prepares for an absolute capacity
* clarify that, to the contrary, ensureStorageCapaciy() means the delta
Moreover, it turns out that the assertion regarding storage limits
triggers frequently while writing the test code; so we can conclude
that the `AllocationCluster` interface lures into allocating without
previous check. Consequently, this check now throws a runtime exception.
As an aside, the size limitation should be accessible on the interface,
similar to `std::vector::max_size()`
By means of the extension point, which produces a dedicated policy
for use with `AllocationCluster`, it becomes possible to use the
specialised API to adjust the latest allocation in the cluster.
When this is not actually usable, the policy will fall back
on the standard implementation (which is wasteful when
applied to `AllocationCluster`, since memory for the
obsoleted, smaller blocks not de-allocated then...
- decided to allow creating empty lib::Several;
no need to be overly rigid in this point,
since it is move-assignable anyway...
- populate with enough elements to provoke several reallocations
with copying over the existing elements
- precisely calculate and verify the expected allocation size
- verify the use-count due to dedicated allocator instances
being embedded into both the builder and hidden in the deleter
- move-assign data
- all checksums go to zero at end
The setup for `ArrayBucket` is special, insofar it shell de-allocate itself,
which creates the danger of re-entrant calls, or to the contrary, the danger
to invoke this clean-up function without actually invoking the destructor.
These problems become relevant once the destructor function itself is statefull,
as is the case when embedding a non-trivial, instance bound allocator
to be used for the clean-up work. Using the new `lib::TrackingAllocator`
highlighted this potential problem, since the allocator maintains a use-count.
Thus I decided to move the »destruction mechanics« one level down into
a dedicated and well encapsulated base class; invoking ArrayBucket's destructor
thereby becomes the only way to trigger the clean-up, and even ElementFactory::destroy()
can now safely check if the destructor was already invoked, and otherwise
re-invoke itself through this embedded destructor function. Moreover,
as an additional safety measure, the actual destructor function is now
moved into the local stack frame of the object's destructor call, removing
any possibility for the de-allocation to interfere with the destructor
invokation itself
part of the observed deviation stems form bugs in logging and checksum calculation;
but there seems to be a real problem hidden in the allocator usage of the
new component, since the use-cnt of the handle does not drop to zero
While there might be the possibility to use the magic of the standard library,
it seems prudent rather to handle this insidious problem explicitly,
to make clear what is going on here.
To allow for such explicit alignment handling, I have now changed the
scheme of the storage definition; the actual buffer now starts ''behind''
the `ArrayBucket<I>` object, which thereby becomes a metadata managing header.
__To summarise the problem__: since we are maintaining a dynamically sized buffer,
and since we do not want to expose the actual element type through the
front-end object, we're necessarily bound to perform a raw-memory allocation.
This is denoted in bytes, and thus the allocator can no longer manage
the proper alignment automatically. Rather, we get a storage buffer with
just ''some accidental'' alignment, and we must care to request a sufficient
overhead to be able to shift the actual storage area forward to the next
proper alignment boundary. Obviously this also implies that we must
store this individual padding adjustment somewhere in the metadata,
in order to be able to report the correct size of the block later
on de-allocation.
The solution implemented thus far turns out to be not sufficient
for ''over-aligned-data'', as the raw-allocator can not perform the
''magic work'' because we're exposing only `std::byte` data.
This adaptor works in concert with the generic allocator
building blocks (prospective ''Concepts'') and automatically
registers a either static or dynamic back-link to the factory
for clean-up.
Use this wrapper fore more in-depth test of the new `TrackingAllocator`
and verify proper behaviour through the `EventLog`
- create two vectors, attached to the `TrackingAllocator`
- emplace Tracker-Objects
- move an object to the other vector
- destroy the containers
🠲 Event-Log looks plausible!
- use a meta-registry of pools
- retrieve and manage the `MemoryPool` instances by shared_ptr, with a weak registry entry
- use a hastable for the allocations, keyed by the allocated memory address
- ability to verify a hash-checksum
- ability to watch number of allocations and allotted bytes
- using either a common global pool or a separate dedicated pool
- log all operations into a common `EventLog` instance
- front-end adaptors for use as C++ custom allocator
...these features are now used quite regularly,
and so a dedicated documentation test seems indicated.
Actually my intention is to add a tracking allocator to these test helpers
(and then to use that to verify the custom allocator usage of `lib::Several`)
Phew... this was a tough one — and not sure yet if this even remotely works...
Anyway, the `lib::SeveralBuilder` is already prepared for collaboration with a
custom allocator, since it delegates all memory handling through a base policy,
which in turn relies on std::allocator_traits.
The challenge however is to find a way...
* to make this clear and easy to use
* to expose an extension point for specific tweaks
* and to make all this work without excessive header cross dependencies
This is a low-level interface to allow changing the size of
the currently latest allocation in `AllocationCluster`; a client
aware of this capability can perform a real »in-place re-alloc«,
assuming the very specific usage constraints can be met.
`lib::Several<X>` will use this feature when attached to an
`AllocationCluster`; with this special setup, an previously
unknown number of non-copyable objects can be built without
wasting any storage, as long as the storage reserve in the
current extent of the `AllocationCluster` is sufficient.
...use some pointer arithmetic for this test to verify
some important cases of object placement empirically.
Note: there is possibly a very special problematic case
when ''over aligned objects'' are not placed in accordance
to their alignment requirements. Fixing this problem would
be non-trivial, and thus I have only left a note in #1204
...including the interesting cases where objects are relocated
and the element spread is changed. With the help of the checksum
feature built into the test-dummy objects, the properly balanced
invocation of constructors can be demonstrated
PS: for historical context...
Last week the "Big F**cking Rocket" successfully performed the
test flight 4; both booster and Starship made it back to the
water surface and performed a soft splash-down after decelerating
to speed zero. The Starship was even able to maintain control
in spite of quite some heat damage on the steering flaps.
Yes ... all techies around the world are thrilled...
- spread change now retains the nominal element reserve
- `capacity()` and `capReserve()` now exposed on the builder API
- factor out the handling check safety functions
- rewrite the `resize()` builder function to be more generic
__Test now covers__ example with trivial data type, which can
indeed be resized and allows to grow buffer on-the fly without
requiring any knowledge of the actual type (due to using `memmove`)
building on the preceding analysis, we can now demonstrate that
the container is initially able to grow, but looses this capability
after accepting one element of unknown subclass type...
`lib::Several` is designed to be highly adaptable, allowing for
several quite distinct usage styles. On the downside, this requires
to perform some checks at runtime only, since the ability to handle
some element depends on specific circumstances.
This is a notable difference to `std::vector`, which is simply not capable
of handling ''non-copyable'' types, even if given an up-front memory reservation.
The last test case provided with the previous changeset did not trigger
an exception, but closer investigation revealed that this is correct,
since in this specific situation the container can accept this object type,
thereby just loosing the ability to move-relocate further objects.
A slightly re-arranged test scenario can be used to demonstrate this fine point.
- the test-dummy objects need a `noexcept` move ctor
- **bug** here: need an explicit check to prevent other types
than the known element type from ''sneaking in''
The `SeveralBuilder` is very flexible with respect to added elements,
but it will investigate the provided type information and reject any
further build operation that can not be carried out safely.
...turns out that we must ensure to pass a plain "object" type
to the standard allocator framework (no const, no references).
Here, ''object in C++ terminology'' means a scalar or record type,
but no functor, no references and no void,
Consider what (not) to support.
Notably I decided ''not to support'' moving out of an iterator,
since doing so would contradict the fundamental assumptions of
the »Lumiera Forward Iterator« Concept.
Start verifying some variations of element placement,
still focussing on the simple cases
Parts of the decision logic for element handling was packaged
as separate »strategy« class — but this turned out to be neither
a real abstraction, nor configurable in any way. Thus it is better
to simplify the structure and turn these type predicates into simple
private member functions of the SeveralBuilder itself
Elements maintained within the storage should be placed such
as to comply with their alignment requirements; the element spacing
thus must be increased to be a multiple of the given type's alignment.
This solution works in most common cases, where the alignement is
not larger as the platform's bus width (typically 64bit); but for
''over-aligned types'' this scheme may still generate wrong object
start positions (a completely correct solution would require to
add a fixed offset to the beginning of the storage array and also
to capture the alignment requirements during population and to
re-check for each new type.
...and the nice thing is, the recently built `IterIndex` iteration wrapper
covers this functionality right away, simply because `lib::Several`
is a generic container with subscript operator.
...passes the simplest unit test
* create a Several<int>
* populate from `std::initializer_list`
* random-access to elements
''next step would be to implement iteration''
After some fruitless attempts, I settled for using std::function directly,
in order to establish a working baseline of this (tremendously complicated)
allocation logic. Storing a std::function in the ArrayBucket is certainly
wasteful (it costs 4 »slots« of memory), but has the upside that
it handles all those tricky corner cases magically; notably
the functor can be stored completely inline in the most relevant
case where the allocator is a monostate; moreover we bind a lambda,
which can be optimised very effectively, so that in the simplest case
there will be only the single indirection through the ''invoker''.
This **completes the code path for a simple usage cycle**
🠲 ''and hooray ... the test crashes with a double-free''
- ensure the ''deleter function'' is invoked
- care for proper ''deleter'' setup in case of exception while copying
- need to »lock-in« on one specific kind of ''destructor invocation scheme,''
since we do not keep track of individual concrete element types
Parts of this logic were first coded down in the `realloc` template method,
where it did not really belong; thus reintegrate similar logic one level above,
in the SeveralBuilder::adjustStorage(). Moreover, for performance reasons,
always start with an initial chunk, similar to what `std::vector` does...
since this is meant as a policy implementation, reduce it to the bare operation;
the actual container storage handling logic shall be implemented in the container
and based on those primitive and configurable base operations
...still fighting to get the design of the `AllocationPolicy`
settled to work well with `AllocationCluster` while also allowing
to handle data types which are (not) trivially copyable.
This changeset attempts to turn the logic round: now we capture
an ''move exclusion flag'' and otherwise allow the Policy to
decide on its own, based on the ''element type''
- verifies if new element can just fit in
- otherwise ensure the storage adjustments are basically possible
- throw exception in case the new element can not be accommodated
- else request possible storage adjustments
- and finally let the allocator place the new element
Draft skeleton of the logic for element creation.
This turns out to be a rather challenging piece of code,
since we have to rely on logical reasoning about properties
of the element types in order to decide if and how these
elements can be emplaced, including the possibility to
re-allocate and move existing data to a new location.
- if we know the exact element type, we can handle any
copyable or movable object
- however, if the container is filled with a mixture of types,
we can not re-allocate or grow dynamically, unless all data
is trivially copyable (and can thus be handled through memmove)
- moreover we must ensure the ability to invoke the proper destructor
In-depth analysis of storage management revealed a misconception
with respect to possible storage optimisations, requiring more
metadata fields to handle all corner cases correctly.
It seems prudent to avoid any but the most obvious optimisations
and wait for real-world usage for a better understanding of the
prevalent access patterns. However, in preparation for any future
optimisations, all access coordination and storage metadata is
now relocated into the `ArrayBucket`, and thus resides within the
managed allocation, allowing for localised layout optimisations.
To place this into context: the expected prevalent use case is
for the »Render Nodes Network«, which relies on `AllocationCluster`
for storage management; most nodes will have only a single predecessor
or successor, leading to a large number of lib::Several intsances
populated with a single data element. In such a scenario, it is
indeed rather wasteful to allocate four »slot« of metadata for
each container instance; even more so since most of this
metadata is not even required in such a scenario.
...which basically ''seems doable'' now, yet turns up several unsolved problems
- need a way to handle excess storage for the raw allocation
- generally should relocate all metadata into the ArrayBucket
- mismatch at various APIs; must re-think where to pass size explicitly
- unclear yet how and where to pass the actual element type to create
...turns out to be rather challenging, due to the far reaching requirements
* the default case (heap allocation) ''must work out-of-the box''
* optionally a C++ standard conformant `Allocator` can be adapted
* which works correct even in case this allocator is ''not a monostate''
* **essential requirement** is to pass an `AllocationCluster` reference directly
* need a ''generic extension point'' to adapt to similar elaborate custom schemes
__Note__: especially we want to create a direct collaboration between the allocation policy and the underlying allocator to allow support for a dedicate ''realloc operation''
