Investigate potential improvements to `Key.equals()`

[DomGarguilo]

It appears that improvements could be made to Key.equals(). From the original jira ticket regarding this idea:

In the Key.equals(Key, PartialKey) overload, the current method compares starting at the beginning of the key, and works its way toward the end. This functions correctly, of course, but one of the typical uses of this method is to compare adjacent rows to break them into larger chunks. For example, accumulo.core.iterators.Combiner repeatedly calls this method with subsequent pairs of keys.

I have a patch which reverses the comparison order. That is, if the method is called with ROW_COLFAM_COLQUAL_COLVIS, it will compare visibility, cq, cf, and finally row. This (marginally) improves the speed of comparisons in the relatively common case where only the last part is changing, with less complex code.

I'm not sure why the changes proposed in the jira ticket were never merged, but this idea resurfaced when Key.equals() was identified in #1099. At first, I considered including the improvements of Key.equals() as part of the PR for #1099, but I don't think that this sort of improvement will make much, if any, difference towards the goal of #1099 so creating a separate ticket/PR seemed like the best option.

[DomGarguilo]

I've run an updated version of the benchmark from the original jira ticket and the results I received seem significant

Benchmark                    Mode  Cnt   Score   Error  Units
MyBenchmark.customDom       thrpt   25  56.241 ± 0.458  ops/s
MyBenchmark.customVanilla   thrpt   25  53.248 ± 0.475  ops/s
MyBenchmark.customWill      thrpt   25  92.400 ± 0.935  ops/s
MyBenchmark.standardEquals  thrpt   25  51.610 ± 0.470  ops/s

The MyBenchmark.customWill is the relevant equals() method with its comparison reversed. This looks like this:

  public boolean willEquals(WillKey other, PartialKey part) {
    switch (part) {
      case ROW_COLFAM_COLQUAL_COLVIS_TIME_DEL:
        if (deleted != other.deleted)
          return false;
      case ROW_COLFAM_COLQUAL_COLVIS_TIME:
        if (timestamp != other.timestamp)
          return false;
      case ROW_COLFAM_COLQUAL_COLVIS:
        if (!isEqual(colVisibility, other.colVisibility))
          return false;
      case ROW_COLFAM_COLQUAL:
        if (!isEqual(colQualifier, other.colQualifier))
          return false;
      case ROW_COLFAM:
        if (!isEqual(colFamily, other.colFamily))
          return false;
      case ROW:
        return isEqual(row, other.row);
      default:
        throw new IllegalArgumentException("Unrecognized partial key specification " + part);
    }
  }

Compared to the current code: https://github.com/apache/accumulo/blob/36dd78ce6bbc2aae8db72014b8703f94b9b92ded/core/src/main/java/org/apache/accumulo/core/data/Key.java#L977-L1002 I did add another equals method to the benchmark for testing in relation to #2811 represented by MyBenchmark.customDom in the benchmark printout. For those interested that method can be found here.

[EdColeman]

Maybe I am reading you code wrong, but I don't see where your code is functionally equivalent to the current code that you posted here.

The current code seems to be performing partial key comparisons - so for example, if the case is ROW only the row data is compared. If it was ROW_COLFAM_COLQUAL the fields ROW, COL_FAM and COL_QUAL are all checked - it looks like you code only checks the last value as specified by the depth.

With your code, if the timestamps are equal, would it consider the rows equal?

What I thought you were going for would use boolean operation short-circuiting so that comparing "long" rows would be deferred until later.

original: 
...
case ROW_COLFAM_COLQUAL_COLVIS_TIME_DEL: 
 return isEqual(row, other.row) && isEqual(colFamily, other.colFamily) 
           && isEqual(colQualifier, other.colQualifier) 
           && isEqual(colVisibility, other.colVisibility) && timestamp == other.timestamp 
           && deleted == other.deleted; 

possible change:
...
case ROW_COLFAM_COLQUAL_COLVIS_TIME_DEL: 
 return deleted == other.deleted &&
           && timestamp == other.timestamp 
           && isEqual(colVisibility, other.colVisibility)
           && isEqual(colQualifier, other.colQualifier) 
           && isEqual(colFamily, other.colFamily) 
           && isEqual(row, other.row) 

However, even this may end up with additional comparisons and would depend on the distribution of values within the table.

When comparing full depth, checking isDeleted and timestamp upfront seem to be a good optimization.

When comparing a partial key, things are not so clear cut.

• Visibilities may or may not change frequently.
• If locality groups are used, then column family / column qualifiers will be grouped together and then less likely to change from row to row.
• for changes between row(s), the last bytes are more likely to change the fastest. if the rows are AAAA and AAAB starting from the end (when lengths are equal) requires one comparison. Starting from the head it takes four comparisons (assuming checking one character at a time, but holds for longer values when greater than a long or an integer if grabbing multiple bytes at a time)

Sorry if I misunderstand what you are showing.

[DomGarguilo]

@EdColeman, I think you are understanding things correctly. The code I posted above was from the original ticket and I had overlooked the points you have made. I'll work on some changes to try to address these things.

[EdColeman]

Looking at the method in 'Key' the method that performs the equality check on a byte array private static boolean isEqual(byte[] a1, byte[] a2) is already optimized for Accumulo row comparisons, checking the last few bytes first and does not seem to need additional optimization.

[DomGarguilo]

Looking at the method in 'Key' the method that performs the equality check on a byte array private static boolean isEqual(byte[] a1, byte[] a2) is already optimized for Accumulo row comparisons, checking the last few bytes first and does not seem to need additional optimization.

So then maybe the only thing that might be worth looking into further is your suggestion about the full depth check:

When comparing full depth, checking isDeleted and timestamp upfront seem to be a good optimization.

[EdColeman]

I am confused with the in the context of #2811 are any changes needed?

If not, changing the full depth equals to deleted, timestamp, row, col fam, col qual and then col visibility might be a minor improvement. deleted and timestamp should be easy checks, keeping the rest of the order (row, col fam,...) minimizes behavior changes - in some cases having vis, col fam, col qual checked before large row values would help, but in other cases it would be worse - so without evidence of a general improvement without negative impacts it seems safest to leave that part of the current order in place.

[DomGarguilo]

I am confused with the in the context of #2811 are any changes needed?

No changes are needed in the sense that they don't fix any bugs or change any behavior, but they reduce the size of some of the methods which makes them no longer "hot".

[DomGarguilo]

I ended up making a github repository for benchmarking various versions of Key.equals(). The repo can be found at https://github.com/DomGarguilo/key-equals-benchmark

Some of the results I got from running the benchmark:

With random PartialKey

Benchmark                      Mode  Cnt   Score   Error  Units
MyBenchmark.customVanilla     thrpt   25  27.139 ± 0.286  ops/s
MyBenchmark.customVanilla2    thrpt   25  28.130 ± 0.182  ops/s
MyBenchmark.refactoredEquals  thrpt   25  27.282 ± 0.096  ops/s

With deepest PartialKey only (ROW_COLFAM_COLQUAL_COLVIS_TIME_DEL)

Benchmark                      Mode  Cnt   Score   Error  Units
MyBenchmark.customVanilla     thrpt   25  47.726 ± 0.422  ops/s
MyBenchmark.customVanilla2    thrpt   25  74.062 ± 0.438  ops/s
MyBenchmark.refactoredEquals  thrpt   25  53.445 ± 0.557  ops/s

The run in the benchmark can be viewed here.

customVanilla - copied over the code for Key.equals() customVanilla2 - same as current equals function just the delete and timestamp are evaluated first for the PartialKey.ROW_COLFAM_COLQUAL_COLVIS_TIME_DEL case (as suggested by @EdColeman in a comment above) refactoredEquals - refactored to reuse code and make the method smaller

It is probably important to take note of how the data is being produced and other factors before drawing any conclusions here.

From the results above it seems like both of the other versions of this method are (potentially negligibly) more performant than the current code. The refactoredEquals method also has the advantage of not being "hot" (elaborated here).

I think I need some input on these benchmarks and their findings to determine if anything significant can be drawn from them. Specifically, how the data in the benchmark is being produced and the structure of the benchmark in general.