A Flyweight pattern is one approach. Something like

class FlyweightColumns
{
  ByteBuffer[] names;
  ByteBuffer[] values;
  long[] timestamps;

  private class FlyweightColumn implements IColumn
  {
    private final int index;

    public ByteBuffer name()
    {
      return names[index];
    }

    ... 
  }
}

I note that the reason we need to support add-not-in-sorted-order and replace is purely counters. CASSANDRA-4775 could fix that.

Per the discussion on CASSANDRA-5043, add doesn't need to support out-of-order; only replace does.

And I don't think the replace we have is any problem for the flyweight pattern, since all we support is replacing a column by another with the same name. I.e. this is really an in-place replace only.

Actually, thinking about this issue a bit more, I'm wondering: what is it we expect to win here?

Because we will still need to allocate one FlyweightColumn object per actual column. So in terms of sheer number of allocated objects, we'll have the same number (in fact we'll even have marginally more ojbects since we'll have to allocate the FlyweightColumns names, values and timestamps arrays).

Now it's true that the memory layout will be slightly different, with the FlyweightColumn objects being slightly smaller than their Column counterpart (though overall we won't allocate less memory), but I'm not sure it makes much difference for the GC since the size difference is relatively minor. And on the other side, the circular dependency of FlyweightColumns to it's child FlyweightColumn might make the job of the GC a bit harder (it's more links to explore). Overall, it's far from obvious to me that it would improve things in a measurable way.

And doing that would also mess a bit with the ColumnSerializer, as we would want it to create a flyweightColumn right away, meaning that it's not just an alternative ISortedColumn implementation, the abstraction would leak out.

So am I missing something here and not understanding that idea at all?

You're right. It would need to be more like this:

class FlyweightColumns
{
  ByteBuffer[] names;
  ByteBuffer[] values;
  long[] timestamps;

  private int index;
  private FlyweightColumn instance = new FlyweightColumn();

  public IColumn getColumn(int i)
  {
     index = i;
     return instance;
  }

  private class FlyweightColumn implements IColumn
  {
    public ByteBuffer name()
    {
      return names[index];
    }

    ... 
  }
}

Obviously some caution would be required (like ABSC, this is not suitable for Memtable or cache use) but this would be totally adequate for the main "read some columns for the user, then serialize them back to the coordinator" path.

For more OO sugar we could move operations like "serialize columns to this OutputStream" into ISortedColumns instead of exposing getColumn(int) directly, I include that mainly because it is the easiest way to illustrate the FWC re-use.

I'm really not a fan. Doing that means we break the 'Column is an immutable object' assumption and it would make getting code right much harder. Typically, for a ColumnFamily backed byt such backing FlyweightColumns, you'd have to be extra careful when using it to never alias a Column returned during iteration because that alias would be invalidated by the next step of the iteration itself. I'm really afraid this would make it far too easy to get subtle bugs.

Unless it can be demonstrated that such a thing brings concrete and substantial performance benefits, I think I'm -1 on it cause it would make imo the code too much fragile.

Let's see if it's a benchmark win, if it is then we can go about trying to make it safe, e.g. w/ the kind of encapsulation I described.

What makes this a bitch is that we ask our Iterators for Column objects, which we then add to the ColumnFamily. So we can't just drop in a FlyweightColumns CF subclass; the damage is already done by then.

We'd have to push the CF into OnDiskAtomIterator and have it call add(name, value, timestamp) to avoid the Column construction overhead.

Want to give this a try, Carl Yeksigian?

Possibly useful: https://github.com/RichardWarburton/slab

We could just allocate a new flyweight Column object when we want to read it. In most cases the reference is unlikely to escape, and they'll be allocated on stack.

Presumably in cases where they do escape we can either stop them from doing so or introduce some new method that converts them to a heavyweight Column. Not that this is likely to be a small task, having a look at it. Might be worth comparing performance with just this change and minimal optimisation work to see how it fairs, though?

Hmm, I'm not sure what you're thinking of, but I'm talking about the main getColumnFamily -> CollationController path where we need to collect Columns into a ColumnFamily object so we can write them out to the wire. I don't think local Columns play a large role there. (If they did, couldn't we just avoid allocating a Column in the first place and just leave the raw fields on the stack?)

Major overhaul, so suggested with caution, but why don't we pass a context that knows what to do with the results, and is furnished with them as they are found by the CollationController? There's no real need to construct a Row at any point - in fact it looks like it gets translated straight into a List<List<ByteBuffer>> at the end anyway.

Look at ReadVerbHandler; we do need a Row to serialize.

Ah, my mistake, I was looking at the CQL query processor. Either way, not to push the issue, but it's not absolutely necessary; an IncrementalRowSerializer (with an IncrementalColumnFamilySerializer) or similar could be defined which collects the atoms and serializes them immediately. Only needs to be used as an optimisation on the common code paths to make a big difference, and the remainder could simply invoke a wrapper method that constructs the Row as usual. The Row/ColumnFamily serializers could trivially be switched to calling these incremental serializers, so no code duplication, hot code paths can be updated without tremendous effort, and infrequent code paths take an imperceptible performance hit (given the context will be stack allocated it is unlikely to be measureable).