[
https://issues.apache.org/jira/browse/CASSANDRA-2843?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel
]
Sylvain Lebresne updated CASSANDRA-2843:
----------------------------------------
Attachment: microBenchmark.patch
bq. "this implementation should not expect the input always come in already
sorted order"
Yeah, that's not really what I said. I said that it should not *assume* it.
Which doesn't mean it cannot optimize for it. If you look at the version I
attached, at least as far a addColumn is concerned, it does the exact same
thing as your version, with the only difference that I first check if adding at
the tail is legit and fail back to a binary search if that is not the case.
That is, as long as the input is in sorted order, it will be as fast as your
implementation (there is one more bytebuffer comparison but I'm willing to bet
that it has no noticeable impact on performance). But it won't create unsorted
CF if the input is not in sorted order.
Btw, Yang, can you try to fix you 3 last comments ?
bq. If the main benefit is avoiding synchronization, shouldn't we just stick w/
TreeMap for simplicity?
I'm attaching a second patch with the micro-benchmark that I've used and the
TreeMap implementation so that people can look for themselves. The test simply
creates a CF, add columns to it (in sorted order) and do a simple iteration at
the end. I've also add a delete at the end because at least in the case of
super columns, we do call removeDeleted so the goal was to see if this has a
significant impact (the deletes are made at the beginning of the CF, which is
the worst case for the ArrayBacked solution). The test also allow to have some
column overwrap (to exercise reconciliation). Not that when that happens, the
input is not in strict sorted order anymore, but it's mostly at the
disadvantage of the ArrayBack implementation there too. Playing with the
parameters (number of columns added, number that overlaps, number of deletes)
the results seems to always be the same. The ArrayBacked is consistently faster
than the TreeMap one that is itself consistently faster than the CSLM one. Now
what I meant is that the difference between ArrayBacked and TreeMap is
generally not as big as the one with CSLM, but it is still often very
noticeable.
This is no surprise in the end, the ArrayBacked solution is optimized for
insertion in sorted order: the insertion is then O(1) and with a small constant
factor because we're using ArrayList. TreeMap can't beat that. Given this, and
given that ColumnFamily is one of our core data structure, I think we should
choose the more efficient implementation for each use case. And truth is, the
ArrayBacked implementation is really not very complicated, that's basic stuff.
bq. That's odd, because adding in sorted order is actually worst-case for CSLM,
and that's what we do on reads.
Yeah, I was a bit quick on that statement. Rerunning my micro-benchmarks does
show that we're much much faster even without reconciliation happening.
> better performance on long row read
> -----------------------------------
>
> Key: CASSANDRA-2843
> URL: https://issues.apache.org/jira/browse/CASSANDRA-2843
> Project: Cassandra
> Issue Type: New Feature
> Reporter: Yang Yang
> Attachments: 2843.patch, fast_cf_081_trunk.diff, microBenchmark.patch
>
>
> currently if a row contains > 1000 columns, the run time becomes considerably
> slow (my test of
> a row with 30 00 columns (standard, regular) each with 8 bytes in name, and
> 40 bytes in value, is about 16ms.
> this is all running in memory, no disk read is involved.
> through debugging we can find
> most of this time is spent on
> [Wall Time] org.apache.cassandra.db.Table.getRow(QueryFilter)
> [Wall Time]
> org.apache.cassandra.db.ColumnFamilyStore.getColumnFamily(QueryFilter,
> ColumnFamily)
> [Wall Time]
> org.apache.cassandra.db.ColumnFamilyStore.getColumnFamily(QueryFilter, int,
> ColumnFamily)
> [Wall Time]
> org.apache.cassandra.db.ColumnFamilyStore.getTopLevelColumns(QueryFilter,
> int, ColumnFamily)
> [Wall Time]
> org.apache.cassandra.db.filter.QueryFilter.collectCollatedColumns(ColumnFamily,
> Iterator, int)
> [Wall Time]
> org.apache.cassandra.db.filter.SliceQueryFilter.collectReducedColumns(IColumnContainer,
> Iterator, int)
> [Wall Time] org.apache.cassandra.db.ColumnFamily.addColumn(IColumn)
> ColumnFamily.addColumn() is slow because it inserts into an internal
> concurrentSkipListMap() that maps column names to values.
> this structure is slow for two reasons: it needs to do synchronization; it
> needs to maintain a more complex structure of map.
> but if we look at the whole read path, thrift already defines the read output
> to be List<ColumnOrSuperColumn> so it does not make sense to use a luxury map
> data structure in the interium and finally convert it to a list. on the
> synchronization side, since the return CF is never going to be
> shared/modified by other threads, we know the access is always single thread,
> so no synchronization is needed.
> but these 2 features are indeed needed for ColumnFamily in other cases,
> particularly write. so we can provide a different ColumnFamily to
> CFS.getTopLevelColumnFamily(), so getTopLevelColumnFamily no longer always
> creates the standard ColumnFamily, but take a provided returnCF, whose cost
> is much cheaper.
> the provided patch is for demonstration now, will work further once we agree
> on the general direction.
> CFS, ColumnFamily, and Table are changed; a new FastColumnFamily is
> provided. the main work is to let the FastColumnFamily use an array for
> internal storage. at first I used binary search to insert new columns in
> addColumn(), but later I found that even this is not necessary, since all
> calling scenarios of ColumnFamily.addColumn() has an invariant that the
> inserted columns come in sorted order (I still have an issue to resolve
> descending or ascending now, but ascending works). so the current logic is
> simply to compare the new column against the end column in the array, if
> names not equal, append, if equal, reconcile.
> slight temporary hacks are made on getTopLevelColumnFamily so we have 2
> flavors of the method, one accepting a returnCF. but we could definitely
> think about what is the better way to provide this returnCF.
> this patch compiles fine, no tests are provided yet. but I tested it in my
> application, and the performance improvement is dramatic: it offers about 50%
> reduction in read time in the 3000-column case.
> thanks
> Yang
--
This message is automatically generated by JIRA.
For more information on JIRA, see: http://www.atlassian.com/software/jira
