Reduce map entry allocations computing filtered map size

schlosna commented 6 months ago

General

Before this PR:

From a JFR for an AtlasDB client service, noticed significant allocations of java.util.AbstractMap$SimpleImmutableEntry due to computing the size() of a Guava filtered Map as it creates an entry for each row.

We can avoid this allocation completely by just counting the non-tombstoned values directly.

Class                                       Alloc Total     Total Allocation (%)
java.util.AbstractMap$SimpleImmutableEntry  42.4 GiB        8.039921725418923 %

Stack Trace                                                                                                                                                           Count  Percentage
com.google.common.collect.ImmutableSortedMap$1EntrySet$1.get(int):838                                                                                                 707    99.7 %
   com.google.common.collect.ImmutableSortedMap$1EntrySet$1.get(int):835                                                                                              706    99.6 %
      com.google.common.collect.ImmutableList$1.get(int):412                                                                                                          706    99.6 %
      com.google.common.collect.AbstractIndexedListIterator.next():82                                                                                                 706    99.6 %
      com.google.common.collect.Collections2$FilteredCollection.size():224                                                                                            233    32.9 %
         com.google.common.collect.ForwardingCollection.size():68                                                                                                     233    32.9 %
         java.util.AbstractMap.size():85                                                                                                                              233    32.9 %
         com.palantir.atlasdb.transaction.impl.SnapshotTransaction.removeEmptyColumns(Map, TableReference):893                                                        232    32.7 %
            com.palantir.atlasdb.transaction.impl.SnapshotTransaction.filterRowResults(TableReference, Map, ImmutableMap$Builder):886                                 232    32.7 %
            com.palantir.atlasdb.transaction.impl.SnapshotTransaction.getRowsInternal(TableReference, Iterable, ColumnSelection):464                                  232    32.7 %
            com.palantir.atlasdb.transaction.impl.SnapshotTransaction.getRows(TableReference, Iterable, ColumnSelection):426                                          232    32.7 %
            com.palantir.atlasdb.transaction.impl.SerializableTransaction.getRows(TableReference, Iterable, ColumnSelection):210                                      230    32.4 %
            com.palantir.atlasdb.transaction.impl.ReadTransaction.getRows(TableReference, Iterable, ColumnSelection):61                                               2      0.282 %
         com.google.common.collect.Maps$FilteredEntryNavigableMap.size():3353                                                                                         1      0.141 %
            com.palantir.atlasdb.transaction.impl.SnapshotTransaction.lambda$filterEmptyColumnsFromRows$29(TableReference, RowResult):1372                            1      0.141 %
            com.palantir.atlasdb.transaction.impl.SnapshotTransaction$$Lambda$3901+0x000000008183a948.164092742.apply(Object):-1                                      1      0.141 %
            com.google.common.collect.Iterators$6.transform(Object):829                                                                                               1      0.141 %
            com.google.common.collect.TransformedIterator.next():52                                                                                                   1      0.141 %
            com.google.common.collect.Iterators$5.computeNext():672                                                                                                   1      0.141 %
            com.google.common.collect.AbstractIterator.tryToComputeNext():146                                                                                         1      0.141 %
            com.google.common.collect.AbstractIterator.hasNext():141                                                                                                  1      0.141 %
            com.google.common.collect.ForwardingIterator.hasNext():52                                                                                                 1      0.141 %
            com.google.common.collect.ForwardingIterator.hasNext():52                                                                                                 1      0.141 %
            com.google.common.collect.Iterators$4.next():641                                                                                                          1      0.141 %
            com.google.common.collect.Iterators$4.next():626                                                                                                          1      0.141 %
            com.palantir.common.base.BatchingVisitableFromIterable.batchAcceptSizeHint(int, AbstractBatchingVisitable$ConsistentVisitor):56                           1      0.141 %
            com.palantir.common.base.AbstractBatchingVisitable.batchAccept(int, AbortingVisitor):42                                                                   1      0.141 %
            com.palantir.common.base.BatchingVisitableFromIterable$SingleCallBatchingVisitable.batchAccept(int, AbortingVisitor):84                                   1      0.141 %
            com.palantir.atlasdb.transaction.impl.SnapshotTransaction.getBatchingVisitableFromIterator(TableReference, RangeRequest, int, AbortingVisitor, int):1332  1      0.141 %

After this PR:

==COMMIT_MSG== Compute filtered size without traversing lazily transformed map size() as that allocates entries.

==COMMIT_MSG==

Priority:

Concerns / possible downsides (what feedback would you like?):

Is documentation needed?:

Compatibility

Does this PR create any API breaks (e.g. at the Java or HTTP layers) - if so, do we have compatibility?:

Does this PR change the persisted format of any data - if so, do we have forward and backward compatibility?:

The code in this PR may be part of a blue-green deploy. Can upgrades from previous versions safely coexist? (Consider restarts of blue or green nodes.):

Does this PR rely on statements being true about other products at a deployment - if so, do we have correct product dependencies on these products (or other ways of verifying that these statements are true)?:

Does this PR need a schema migration?

Testing and Correctness

What, if any, assumptions are made about the current state of the world? If they change over time, how will we find out?:

What was existing testing like? What have you done to improve it?:

If this PR contains complex concurrent or asynchronous code, is it correct? The onus is on the PR writer to demonstrate this.:

If this PR involves acquiring locks or other shared resources, how do we ensure that these are always released?:

Execution

How would I tell this PR works in production? (Metrics, logs, etc.):

Has the safety of all log arguments been decided correctly?:

Will this change significantly affect our spending on metrics or logs?:

How would I tell that this PR does not work in production? (monitors, etc.):

If this PR does not work as expected, how do I fix that state? Would rollback be straightforward?:

If the above plan is more complex than “recall and rollback”, please tag the support PoC here (if it is the end of the week, tag both the current and next PoC):

Scale

Would this PR be expected to pose a risk at scale? Think of the shopping product at our largest stack.:

Would this PR be expected to perform a large number of database calls, and/or expensive database calls (e.g., row range scans, concurrent CAS)?:

Would this PR ever, with time and scale, become the wrong thing to do - and if so, how would we know that we need to do something differently?:

Development Process

Where should we start reviewing?:

If this PR is in excess of 500 lines excluding versions lock-files, why does it not make sense to split it?:

Please tag any other people who should be aware of this PR: @jeremyk-91 @sverma30 @raiju

changelog-app[bot] commented 6 months ago

Generate changelog in changelog-dir>`changelog/@unreleased`</changelog-dir

What do the change types mean?

- `feature`: A new feature of the service. - `improvement`: An incremental improvement in the functionality or operation of the service. - `fix`: Remedies the incorrect behaviour of a component of the service in a backwards-compatible way. - `break`: Has the potential to break consumers of this service's API, inclusive of both Palantir services and external consumers of the service's API (e.g. customer-written software or integrations). - `deprecation`: Advertises the intention to remove service functionality without any change to the operation of the service itself. - `manualTask`: Requires the possibility of manual intervention (running a script, eyeballing configuration, performing database surgery, ...) at the time of upgrade for it to succeed. - `migration`: A fully automatic upgrade migration task with no engineer input required. _Note: only one type should be chosen._

How are new versions calculated?

- ❗The `break` and `manual task` changelog types will result in a major release! - 🐛 The `fix` changelog type will result in a minor release in most cases, and a patch release version for patch branches. This behaviour is configurable in autorelease. - ✨ All others will result in a minor version release.

Type

- [ ] Feature - [x] Improvement - [ ] Fix - [ ] Break - [ ] Deprecation - [ ] Manual task - [ ] Migration

Description

Compute filtered size without traversing lazily transformed map `size()` as that allocates entries.

**Check the box to generate changelog(s)** - [x] Generate changelog entry

svc-autorelease commented 6 months ago

Released 0.1073.0

palantir / atlasdb