2

The problem that I face is how to combine encapsulating and optimal memory use.

I can't show you my code and therefore explain it on extensive (I hope) example.

Let's say we need to have a database of mans. We want to know only 2 things about those people:

  1. Age of the man (in hours from birth).
  2. Name of the town he lives in.

The convenient and natural way to manage this data is to create an object, which corresponds to a man and store it in an array:

class OMan1 {
  public:
    OMan( const int &age, const astring &t ): fAge(age), fTown(t) {}
    const int& age() const: { return fAge; }
    const astring& Town() const: { return fTown; }
    astring FullId() const: { return fTown+fAge; }
  private:
    int fAge;
    astring fTown;
}

OMan mans[N];

Here our OMans are self-containing object and everything fills nice.

Except of the fact that we clone names of the towns thousands of times, and waste memory and execution time this way.

An improvement we can do is to make an independent array for town names and for each OMan, store only the age, an id of the town and a pointer to towns array:

class OMan2 {
  // same functionality as for OMan1
    int fAge;
    int fTownId;
    astring* fTowns;
}

object is still self-contained, sizeof(int) + sizeof(void*) is much less then sizeof(astring), we win a lot. But still it is factor of 2-3 more than sizeof(fAge) and we repeat fTowns billions of times.

Memory optimisation is crucial for me, therefore what I do is keeping only fAge and fTownId and move such functionality as Town() and FullId() out of the OMan class to some class like OManDataBase:

class OMan3 {
  public:
    OMan( const int &age, const int &tid ): fAge(age), fTownId(tid) {}
    const int& age() const: { return fAge; }
    const int& TownId() const: { return fId; }
    // const astring& Town() const: { return fTown; }
    // astring FullId() const: { return fTown+fAge; }
  private:
    int fAge;
    int fTownId;
}

class OManDataBase {
  // constructor, destructor
    const int& age( const int& i) const: { return fMans[i].TownId()]; }
    const astring& Town( const int& i) const: { return fTown[fMans[i].TownId()]; }
    const astring& FullId( const int& i) const: { return Town(i)+age(i); }
  private:
    vector<OMan3> fMans;
    vector<astring> fTowns;
}

And OMan3 now is not self contained object. It doesn't know it's fullname, for instance. That means that if I need to do some data processing with one man I have to use whole OManDataBase instance:

OBillType47 NewBillType47( const OManDataBase &db, int i ) { ... }

instead of

OBillType47 NewBillType47( const OMan &m ) { ... }

encapsulation has been broken here and the code readability has been clearly decreased. (I put Type47 to emphasise that I can have a lot of functions, which works with Oman-S and can't include all of them into OManDataBase class).

I wonder is there any other way(-s) to solve data duplication problem, keeping objects as self-containing as possible?

  • 2
    Look up the Multiton Pattern and related patterns like Flyweight and Factory. – amon Nov 29 '13 at 16:28
  • my previous comment points towards too complicated solutions. I think you'd want a static map that maps strings to strings that are equal, but not necessarily identical to the key. The key can then be discarded. For each key, the returned string object is identical, thus reducing your storage requirements to the map overhead + a pointer. – amon Nov 29 '13 at 17:05
4

You should try to use the Flyweight pattern. This means, you will store only the town id in the man object, and the method for getting the Town name will still be part of your "man" object. To make this work, you have to pass the list of all towns as a parameter:

class OMan1 
{
   //..
   const astring& Town( const vector<astring> &allTowns) const: 
   { 
      return allTowns[fTownId]; 
   }
   // ...
 }

So, you will loose of course some self-containment, since you will have to supply the town list all everywhere where you ask a "man" object for his town, but the Town() method is kept at the place where most people would expect it: in the "man" object, and not in some kind of "god object" (database).

  • I like the idea of "method is kept at the place where most people would expect it", Thanks. Where allTowns can be kept in this case? – klm123 Nov 30 '13 at 8:49
  • @klm123: that heavily depends on the architecture of your program, the lifetime of your objects, where you store objects in general, the need for change the townlist afterwards etc. So without knowing some more details about the context, this question is not answerable. – Doc Brown Nov 30 '13 at 11:35
  • I understand. I just wonder what to do if I use OMan1 in many different objects over the program... I suppose each such an object should keep a reference to allTowns. – klm123 Nov 30 '13 at 11:48
3

Here's some naive advice I hope you find helpful to conserve memory...

Solution 1

Instead of using a C++ class to store the data, use "packed" structures (look at the documentation for your compiler to figure out how to create a packed structure, there's usually a compiler flag involved). Then limit the size of your variables memory footprints, for instance a uint8 should be big enough to store a mans age. Once you've done this store the packed structure in a c style array (for maximum compression) or use std::vector<OManStruct> if you want to make your life easier. Instead of storing the name of the town as a string in the struct, create a std::map<uint32_t, string> that maps townIds to town names. Store the townId in the struct.

Your struct definition might look something like this (if your using GCC):

typedef struct __attribute__((__packed__)) OManStruct 
{
    uint8_t fAge;
    uint32_t fTownId; //maybe you could use uint16_t here but you might be cutting it close
};

Architecturally I would wrap the knowledge of these data structures in a class that maintains the array, associated data (number of elements etc), and exposes some nice getters and setters so the outside world doesn't know about this implementation detail. Or better yet create, an OManFactory which can be treated as a singleton in your project and returns OMan objects on request.

Solution 2

You might want to seriously consider databasing your data using SQLite, Postgres etc or some nosql database like Redis.. If the amount of data is going to grow over time there's no guarantee you might not blow through all your ram even if you implement solution 1. A database would also give you the ability to store the data persistently and give you a nice mechanism (if using an sql type database) for doing queries on the data.

  • "Instead of storing the name of the town as a string in the struct, create a std::map<uint32_t, string> that maps townIds to town names. Store the townId in the struct." Do you mean here something different from my solution with "vector<astring> fTowns;"? – klm123 Nov 30 '13 at 8:44
  • Sorry, but all other thing is not really related to MY question. These are separate problems, which I need to consider taking into account execution time. – klm123 Nov 30 '13 at 8:46
  • klm123 the idea is basically the same except that the map is more robust to changes in the fTowns data structure. Using the vector, should you ever insert or delete elements from the vector, you are hosed. – Ron Nov 30 '13 at 15:26
1

Data duplication vs Encapsulating. Which design to use?

In sufficiently critical contexts, I find a design that doesn't require me to compromise one for the other. If you can't make something self-sufficient without a lot of non-trivial redundancy of a kind that doesn't, say, aid in multithreading, then my solution is to design at a coarser level that doesn't require such compromises.

// Notice "Men", not "Man"
class OMen
{
public:
    ...

private:
    std::vector<int> age;
    std::vector<int> town_idx;
    std::vector<astring> town_names;
};

That's utilizing potentially hot/cold field splitting (though you might combine the age and town index if your critical access patterns are random) and maybe very simplistic string interning (a type of flyweight). This also gives you a boatload of breathing room to tune and tweak the data rep as you need in hindsight without any costly design changes.

Your public interface might still return like a proxy to an OManProxy through operator[] which lets you access it like an object, but it's really just indexing and pointing to data in this aggregate (collection of men) and you use it as a temporary proxy for convenience.

It's like instead of trying to spend all day focusing on how to design a Pixel class that is efficient, zoom out, and instead design an Image class and turn "pixels" into an internal implementation detail of this aggregate. The biggest value of data-oriented design to me is not how to design data efficiently for optimal memory layout and access, but how to model things at a sufficiently coarse level to give you all the breathing room you need to experiment with your data representations, profile, tweak and tune, without costly and intrusive central changes to public interfaces, widely used, because the real thing we want to avoid are costly design changes more than anything else. If you model teeny little objects that barely store any data that are widely used, then you've already trapped yourself in a design corner.

This is, of course, for sufficiently critical contexts where you need all the optimization breathing room you can get for the future. It is sometimes a bit more unwieldy in implementation to implement container types of this sort (the analogical Image as opposed to Pixel, or the analogical ParticleSystem as opposed to Particle), especially if you start providing proxies and such for convenient usage. But it beats having a thousand dependencies to like OMan all over the place only to realize its internal representation is in severe need of change in ways that would require changes to its public interface. And that's a useful design strategy in general, not just for performance-critical areas. If you're getting hung up on how to design something miniscule, question if it should really be something public and directly depended on by many places, or if it would be more appropriate to turn it into an implementation detail of some coarser, higher-level, perhaps sometimes more abstract design, because any design which has you constantly second-guessing yourself is probably not one you want to start throwing lots of dependencies at.

0

Flyweight pattern is the right idea.

I found this older Stack Overflow post about the Boost Flyweight Library that might fit your needs. I'm not much of a C++ user and have never used it, so use at your own risk!

0

When deciding just how to build your data structures, ponder the issues involved in relational databases when data is normalized and denormalized

Don't re-invent the wheel because you are looking at the problem from too low a level of detail.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.