Add a class to allocate small objects w/o extra calls to new.

src/core/SkStackAllocator.h

Index: src/core/SkStackAllocator.h
diff --git a/src/core/SkStackAllocator.h b/src/core/SkStackAllocator.h
new file mode 100644
index 0000000000000000000000000000000000000000..8de02977adae070734ef8230e2b7c446cc0c6aec
--- /dev/null
+++ b/src/core/SkStackAllocator.h
@@ -0,0 +1,120 @@
+/*
+ * Copyright 2014 Google, Inc
+ *
+ * Use of this source code is governed by a BSD-style license that can be
+ * found in the LICENSE file.
+ */
+
+#ifndef SkStackAllocator_DEFINED
+#define SkStackAllocator_DEFINED
+
+#include "SkTDArray.h"
+#include "SkTypes.h"
+
+/*
+ *  Helper for using an SkStackAllocator to create a new object.
+ *  @param ptr Raw pointer to typeName. It should be pointing to NULL, since
+ *      its old value will be ignored. After this macro finishes, it will point
+ *      to a new object of type typeName, allocated by the SkStackAllocator,
+ *      which will handle deleting it.
+ *  @param allocator Reference to an SkStackAllocator. Will be used to allocate
+ *      an object of type typeName. It handles deleting the new object in its
+ *      destructor.
+ *  @param typeName type of the new object to create.
+ *  @param args Arguments to pass to the constructor of the new object, in
+ *      parentheses, or () for the default constructor.
+ *
+ *  Sample usage:
+ *  <code>
+ *      SkStackAllocator<100> alloc;
+ *      SkBlitter* blitter (NULL);
+ *      SkSTACK_ALLOCATE(blitter, alloc, SkNullBlitter, ());
+ *  </code>
+ *
+ *  After this line, blitter points to a new SkNullBlitter object, which will
+ *  be destroyed when alloc goes out of scope.
+ */
+#define SkSTACK_ALLOCATE(ptr, allocator, typeName, args)    \
+    void* buf = allocator.reserveT<typeName>();             \
+    SkNEW_PLACEMENT_ARGS(buf, typeName, args);              \
+    ptr = static_cast<typeName*>(buf)
+
+// Used by SkStackAllocator to call the destructor for objects it has
+// allocated.
+template<typename T> void destroyT(void* ptr) {
+   static_cast<T*>(ptr)->~T();
+}
+
+/*
+ *  Template class for allocating small (as defined by kSize) objects on the

[mtklein, 2014/02/27 23:40:54]

This sort of reads like we'll be able to allocate kSize objects, or objects of
size kSize.  It's any number of objects totalling less that kSize bytes, right?

[scroggo, 2014/03/05 20:25:52]

Correct. I've updated the comment. Sound better?

+ *  stack. If an object is larger than kSize, it will be allocated on the
+ *  heap, This class's destructor will handle calling the destructor for each
+ *  object it allocated and freeing its memory.
+ */
+template<size_t kSize> class SkStackAllocator : public SkNoncopyable {

[mtklein, 2014/02/27 23:40:54]

It looked like we're generally using this to allocate a single object of one of
several types.  Is that always true?  I'm curious if enforcing that would make
this smaller.

I've seen code that works a bit like this:

{
  OneOf<int, double, SomeClass> x;
  SomeClass* ptr = x.set<SomeClass>(...);  // SomeClass() called.
  SkASSERT(x.is<SomeClass>());
  // ~SomeClass() called here.
}

I think sizeof(OneOf<a, b, c, ...>) could be as small as the maximum of its
types plus a byte to remember which type is the one set (we wouldn't need to
store pointers to the destructor, and we'd never overflow).

[scroggo, 2014/03/05 20:25:52]

Actually, no. The Sk3DBlitter will be allocated by this object when it has
already allocated one object. Also, the motivation behind this change is so that
I can also allocate another object (the Context object which will be returned by
SkShader::setContext, in a future CL - this change is large enough that I think
it warrants a separate CL).

+public:
+    SkStackAllocator()
+    : fStorageUsed(0)
+    {}
+
+    ~SkStackAllocator() {
+        // Destruct in reverse order, in case an earlier object points to a
+        // later object.
+        while (fObjects.count() > 0) {
+            Triple triple;
+            fObjects.pop(&triple);
+            triple.fKillProc(triple.fObj);
+            // Safe to do if fObj is in fStorage, since fHeapStorage will
+            // point to NULL.
+            sk_free(triple.fHeapStorage);
+        }
+    }
+
+    /*
+     *  Create and return space for a T. The space will be on the stack if
+     *  there is room, or on the heap otherwise. Either way, this class will
+     *  call ~T() in its destructor and free the heap allocation if necessary.
+     *
+     *  The caller MUST create a new T in the returned buffer (using
+     *  SkNEW_PLACEMENT or SkNEW_PLACEMENT_ARGS), as this class will call ~T()
+     *  in its destructor. (FIXME: Can we pass T's constructor's arguments to
+     *  this function so we can create the object as well?)

[bungeman-skia, 2014/02/27 18:26:01]

With perfect forwarding in c++11 you can. With c++03, sadly no (at least not in
general).

[mtklein, 2014/02/27 18:51:02]

A good compromise is to make a few versions:

template <typename T> T* createT();
template <typename T, typename A1> T* createT(A1);
template <typename T, typename A1, typename A2> T* createT(A1, A2);
// Add more as needed;

Template methods only need to be syntactically valid until they're called.  This
means whichever one of these has the right arity will work happily and the
others will fail to compile if someone tries to call it.

[scroggo, 2014/03/05 20:25:52]

Done.

+     */
+    template<typename T> void* reserveT() {
+        const size_t storageRemaining = SkAlign4(kSize) - fStorageUsed;
+        const size_t storageRequired = SkAlign4(sizeof(T));
+        Triple triple;
+        if (storageRequired > storageRemaining) {
+            // Allocate on the heap
+            triple.fHeapStorage = sk_malloc_throw(storageRequired);
+            triple.fObj = static_cast<void*>(triple.fHeapStorage);
+        } else {
+            // There is space in fStorage.
+            triple.fHeapStorage = NULL;
+            SkASSERT(SkIsAlign4(fStorageUsed));
+            triple.fObj = static_cast<void*>(fStorage + (fStorageUsed >> 2));
+            fStorageUsed += storageRequired;
+        }
+        triple.fKillProc = destroyT<T>;
+        fObjects.push(triple);
+        return triple.fObj;
+    }
+
+private:
+    struct Triple {
+        void* fObj;

[mtklein, 2014/02/27 23:40:54]

If you really want to keep things small, we might consider using a tagged
pointer here instead of two.  There are always at least two unused bits at the
bottom of a pointer returned from malloc (due to alignment).

struct Pair {
  uintptr_t fData;
  void (*fKillproc)(void*);

  void setPtr(void* ptr, bool onHeap) {
    fData = uintptr_t(ptr) | uintptr_t(onHeap);
  }

  void* getPtr() {
    return (void*)(fData & (UINTPTR_MAX - 1));
  }

  bool onHeap() {
    return fData & 1 == 1;
  }
}

[scroggo, 2014/03/05 20:25:52]

Interesting idea! Are we guaranteed the bottom bit is unused for fStorage as
well? We'll generally only have a few Triples/Pairs (I've renamed it to Rec,
mimicking other classes). Think it's worth it to save a few pointers?

+        void* fHeapStorage;
+        void  (*fKillProc)(void*);
+
+    };
+
+    // Number of bytes used so far.
+    size_t              fStorageUsed;
+    SkTDArray<Triple>   fObjects;
+    // Pad the storage size to be 4-byte aligned.
+    uint32_t            fStorage[SkAlign4(kSize) >> 2];

[mtklein, 2014/02/27 23:40:54]

Consider storing everything in fStorage?  Does it not defeat the purpose
somewhat to use SkTDArray to store the metadata?  Can we make something like
this work?

[void* deleter] [4-byte N] [N-byte data ...] [void* deleter] [4-byte N] [N-byte
data ...]

[scroggo, 2014/03/05 20:25:52]

That's a very good point. I've removed the SkTDArray to remove its calls to
malloc.

An important consequence of this change is that we now have a limited number of
objects that can be created before we exhaust fStorage.

I can think of a few ways to handle the case of exhausting fStorage:
1) assert or return NULL
2) keep a linked list for more objects
3) make this class templated in both the max number of objects needed and
storage size needed

The downside to (1) is that SkSmallAllocator will suddenly stop working. On the
other hand, if the client is us, and we know what we're doing, maybe that's okay
since we'll always use enough.

With (2), SkSmallAllocator will continue working, but will do more allocations
and have tricky code for a case we probably don't intend. It also means that we
may end up following this path when we really intended this to only create a
couple of objects.

With (3), the client is in charge and should know what to expect.

For my use case, I'll only be using the SkSmallAllocator to create a few
objects. I've gone with option (3), but I could be convinced to take a different
approach. Thoughts?

+};
+// This class only makes sense on the stack.

[mtklein, 2014/02/27 23:40:54]

This doesn't strictly have to be on the stack right?  This could be useful as a
class member, something created on the heap, or even as (shudder) a global.

Nothing in here is actually stack-specific, so maybe we should just rename it
SkSmallAllocator?

[scroggo, 2014/03/05 20:25:52]

Agreed. Renamed SkSmallAllocator.

And I've removed the macro (which wouldn't work since it's a template anyway).

+#define SkStackAllocator(...) SK_REQUIRE_LOCAL_VAR(SkStackAllocator)
+
+#endif // SkStackAllocator_DEFINED