RFC on range design for D2
dsimcha
dsimcha at yahoo.com
Thu Jan 8 08:32:27 PST 2009
== Quote from Andrei Alexandrescu (SeeWebsiteForEmail at erdani.org)'s article
> Benji Smith wrote:
> > bearophile wrote:
> >> 5) The source code of the current algorithm module of D2 is already
> >> very complex to follow, it smells of over-generalization here and
> >> there. Sometimes it's better to reduce the generality of things, even
> >> if that reduces their power a little, to reduce complexity, etc. Tango
> >> code too isn't perfect, but it often looks more human. While you have
> >> created the algorithm module I too have created something similar, but
> >> based on different grounds.
> >
> > Along these same lines, while D is still young, the documentation is
> > often thin, and code examples are scarce.
> >
> > I've been doing a lot of programming lately with Tango, and despite the
> > growing documentation, I've had to refer directly to the Tango source
> > code on more occasions than I can count. Luckily, the Tango sources are
> > well-written and pretty easy to read and understand, and I've had very
> > few problems figuring out how to use the library.
> >
> > I hope the range implementation makes readability a high priority.
> Speaking of examples and readability, and to tie this with the
> discussion on array reallocation, I was curious on an array appender
> built on the output range interface. I've seen a quite complicated array
> builder in digitalmars.d. I wanted a simpler appender that should not do
> worse than the built-in ~= and that works with algorithm2 whenever data
> is written out.
> It turned out quite simple and it improved performance of a large-scale
> data preprocessing task of mine (which involved reading and parsing
> about 1M lines of integers) by 15%. I'd be curious how it fares with
> other tests that you guys may have.
> The idea is very simple: just use D's native append operation, but cache
> the capacity to avoid too many lookups (I understand that that's the
> bottleneck).
> I paste the code below, I'd be indebted if you guys grabbed it and
> tested it.
> Andrei
> struct ArrayAppender(T)
> {
> private T* _buffer;
> private size_t _length;
> private size_t _capacity;
> this(T[] array)
> {
> _buffer = array.ptr;
> _length = array.length;
> if (_buffer) _capacity = .capacity(array.ptr) / T.sizeof;
> }
> size_t capacity() const { return _capacity; }
> void putNext(T item)
> {
> invariant desiredLength = _length + 1;
> if (desiredLength <= _capacity)
> {
> // Should do in-place construction here
> _buffer[_length] = item;
> }
> else
> {
> // Time to reallocate, do it and cache capacity
> auto tmp = _buffer[0 .. _length];
> tmp ~= item;
> _buffer = tmp.ptr;
> _capacity = .capacity(_buffer) / T.sizeof;
> }
> _length = desiredLength;
> }
> T[] release()
> {
> // Shrink-to-fit
> auto result = cast(T[]) realloc(_buffer, _length * T.sizeof);
> // Relinquish state
> _buffer = null;
> _length = _capacity = 0;
> return result;
> }
> }
> unittest
> {
> auto app = arrayAppender(new char[0]);
> string b = "abcdefg";
> foreach (char c; b) app.putNext(c);
> assert(app.release == "abcdefg");
> }
One definite problem that I've just realized is that there's no putNext(T[]).
What if you need to append another array to your ArrayAppender, not just a single
element?
More information about the Digitalmars-d-announce
mailing list