Upgrade to Pro — share decks privately, control downloads, hide ads and more …

Separating Allocation from Code

chrismdp
September 04, 2014

Separating Allocation from Code

My journey started with a challenge that memory allocation was a separate concern to algorithm design, and ended in some quite unexpected discoveries.

chrismdp

September 04, 2014
Tweet

More Decks by chrismdp

Other Decks in Programming

Transcript

  1. class Monster : public Entity { int size; string name;

    int attributes[100]; Animation* animation; ! public: Monster(string const& n, EntityTemplate* t) { size = t->size; name = n; animation = new Animation(n + “.ani”); } }; (
  2. auto it = monsters.begin(); for (; it != monsters.end(); ++it)

    { if ((*it)->size > SMALL) { render(*it); } } ()
  3. ()

  4. “I want to say something about implementing blobs that also

    applies to programming in general. Separate your memory allocation policy from your algorithm code. A higher level module should be used to glue the two together in the most optimal way. It always troubles me to see modules that allocate their own memory…” www.johnmccutchan.com/2011/10/programmer-and-his-blobs.html ()(
  5. class Blob { int8* data; Blob(size_t size) { data =

    new int8[size]; } … }; ! Blob* obj = new Blob(1024); ()(
  6. struct Blob { int8* data; size_t size; }; ! int8

    backend[1024]; Blob blob = { backend, 1024 }; ()(
  7. struct Blob { int8* data; size_t size; }; ! int8*

    backend = new int8[1024]; Blob blob = { backend, 1024 }; ()(
  8. struct Blob { int8* data; size_t size; }; ! int8*

    file = getFileArray(“foo.txt”); Blob blob = { file, 1024 }; ()(
  9. class Blob { char *data; ! public: Blob() : _data(NULL)

    {} Blob(void* data) : data((char*)data) {} ! template <typename T> T* get(unsigned offset) const { return (T*)(_data + offset); } }; (()()
  10. Integer(Blob blob) : _blob(blob) {} ! void set(int value) {

    _blob.set1(0, BL_INT); _blob.set4(1, value); } (()()
  11. Array(Blob blob, unsigned capacity) { _blob = blob; _blob.set1(0, BL_ARRAY);

    _blob.set4(CAPACITY_OFFSET, capacity); _blob.set4(USED_OFFSET, FIRST_VALUE); _blob.set4(SIZE_OFFSET, 0); } ! char data[128]; Blob blob(data) Array array(blob, 128); TYPE CAPACITY USED (13) SIZE (0) 13 0 (()()
  12. RANDOM ACCESS Random access was at least an order of

    magnitude slower for all sizes These blobs aren’t designed for random access ((()()
  13. SEQUENTIAL TRAVERSAL With a map containing 50 vectors of 500

    numbers each: STL implementation was ~20% quicker With a map containing 500 vectors of 50 numbers each: Blob implementation was ~30% quicker ((()()
  14. struct Blob { int8* data; size_t size; }; ! int8

    backend[1024]; Blob blob = { backend, 1024 }; ((())()
  15. TDD: “Write tests first” ! (it’s not about the tests,

    actually, but we’ll let you figure that out) ((())()()
  16. class AiData { char _goalData[GOAL_DATA_SIZE]; char _knData[MAX_ACTORS][ACTOR_K_SIZE]; char _qData[MAX_ACTORS][ACTOR_Q_SIZE]; char

    _sharedKnData[SHARED_K_SIZE]; char _sharedQData[SHARED_Q_SIZE]; }; ! AiData* ai = new AiData; ((())()()
  17. ! CPU Intel Core i5 Haswell L2 cache (512 KB)

    CORE + L1 (64 KB) L3 cache (3,072 KB) Main Memory (16,777,216 KB) Bus CORE + L1 (64 KB) This presentation brought to you by… ((())()()
  18. class Blob { int8* data; Blob(size_t size) { data =

    new int8[size]; } … }; ! Blob* obj = new Blob(1024); ((())()()
  19. Monsters auto it = monsters.begin(); for (; it != monsters.end();

    ++it) { if ((*it)->size > SMALL) { render(*it); } } render() render() render() ((())()()
  20. Monsters auto it = monsters.begin(); for (; it != monsters.end();

    ++it) { // update, then if ((*it)->sizeChanged()) { copyToRender(*it, monstersToRender); } } ((())()()
  21. MonstersToRender auto it = monstersToRender.begin(); for (; it != monstersToRender.end();

    ++it) { render(*it); } render() render() render() ((())(s)()
  22. * * * * * * * * Monsters *

    * * MonstersToRender vector<Monster*> monsters; (l(())(s)p)
  23. M M O M M O M M O M

    M O Monsters M M M MonstersToRender vector<Monster> monsters; Now we’re copying the object not a pointer! (l(())(s)p)
  24. Functional programming We mapping data to data - easy to

    reason about, referential transparency for free You’re copying data (or modifying in place as an optimisation) - levering the properties of immutability.
  25. Gold-plate it! (sometimes) Sometimes you need to keep cleaning code,

    learning and investigating. It’s amazing what you’ll find out. Kent Beck: “I’m in the habit of trying stupid things out to see what happens”
  26. Web developers You’re already doing this kind of work with

    SQL Consider your data before building elaborate and messy OO code. Thinking this way helps to break work into asynchronous jobs. Keep an eye on Gary Bernhardt’s new Structured Design work
  27. C++ developers Check out data-oriented design if you haven’t already

    Be wary of naïve OO design. The future of performance is parallelisation. Don’t write a program that’s hard to parallelise. Unlock the power of modern GPUs
  28. Questions? [email protected] / @chrismdp on Twitter I coach and team

    teams on code quality, agile and BDD I make Sol Trader http://soltrader.net Co-founded Kickstart Academy http:// kickstartacademy.io