FWD » Core Development » Database

In a profiled scenario (#9692), there are 104k calls to BaseRecord.getDirtyIndices. The scenario is changing extent fields inside a for each loop. getDirtyIndices is meant to retrieve a BitSet of dirty indices based on the dirty fields. The back trace I am interested in is the call from Validation.flush:

The implementation is iterating the active offset BitSet using nextSetBit API (in the profiled case there are around 8 such dirty fields in a batch). For each set bit, all indexes are traversed and checked whether they contain the specified dirty field. In my case, there are 9 indexes for that table. As there are 104k calls, usually 8 dirty fields and 9 indexes, this results in 7M calls to BitSet.nextSetBit and a similar count of BitSet.get. This triggers a lot of Own Time. *Important: * in my case, there are no dirty indices because the updated columns are not indexed.

Alternative implementation¶

We can attempt to change the implementation into iterating indexes first. And for each index, we can attempt filer[i].intersets(dirtyOffsets). This way I think we can determine faster if an index is dirty or not, without iterating the dirty offsets / indices in a nested manner. Also, interects seems really fast:

    public boolean intersects(BitSet set) {
        for (int i = Math.min(wordsInUse, set.wordsInUse) - 1; i >= 0; i--)
            if ((words[i] & set.words[i]) != 0)
                return true;
        return false;
    }

There are no invariants to be checked (i.e. recalculateWordsInUse or checkInvariants), it is a straight-forward loop.

Tests¶

We need performance tests for this to confirm the alternative implementation works faster for any arbitrary case. I don't think FWD context can provide such insight, so please consider creating a Java example with trunk implementation and suggested implementation. Please compile a table/report on the times for each configuration (no. of indices, no. of dirtyOffsets, full or not, only indexed props / only non-indexed props / 50/50).

Committed the solution to 9702a.

- The private getDirtyIndices() used to check every index for every dirty offset and clone an index on each match. It now makes one pass over the indices and tests each with intersects() against the requested offsets that are also dirty.
- Early exit: if none of the requested offsets is an indexed field (checked against RecordMeta.allIndexedProps), it returns before allocating anything.
- All-fields-dirty check: the check used for new records now goes through a new containsAll() helper, which allocates nothing, instead of clone + and + equals.
- Return value: it returns null when no index qualifies, as the javadoc already promised. All callers in Validation already handle null.
- Public wrapper: it no longer allocates a filter on each call. It passes indexState's set directly (read only), or null for all indices.

Testing
- A standalone harness ran the old and new logic on 2,000,000 random inputs, covering updates and creates, empty offsets, and partial, full and null filters. There were 0 mismatches.
- Micro-benchmark (the method alone): 1.4–106× faster.

Alex, please review.