[BUG] - Eq instance for txid allocates memory

[karknu]

Internal

Summary
Profiling with cardano-ignite highlighted a performance problem tied to the Eq/Ord instance for txid.

This is the code that is causing performance problems:

oneEraGenTxIdRawHash :: CanHardFork xs => OneEraGenTxId xs -> ShortByteString
oneEraGenTxIdRawHash =
  hcollapse
    . hcmap proxySingle (K . toRawTxIdHash . unwrapGenTxId)
    . getOneEraGenTxId

Every node is expected to talk to 10s or 100s of down stream peers. All of them will present the node with mostly the same txs. To keep track of that and to acknowledge TXs already in our mempool the network layer maintains structures keyed on txid. This turns into a lot of extra allocations even today, and with Leios it will get a lot worse.

A work-around like this in ouroboros-network-api removed the issue, but it would be better if it is fixed in consensus.

-- | Raw byte representation of a transaction identifier.
newtype RawTxId = RawTxId ShortByteString
  deriving newtype (Eq, Ord, Show, NFData, NoThunks)

-- | Abstract over transaction identifiers,
--
-- Laws:
--
-- * If @getRawTxId x == getRawTxId y@ then @x == y@
--   (the raw bytes must uniquely identify the transaction)
class HasRawTxId txid where
  getRawTxId :: txid -> RawTxId 

[jasagredo]

A first step towards resolving this:

• Network will define a class they can call to extract a RawTxId.
• Consensus will implement instances for the blocks, all defining RawTxId ~ SL.TxId.
• In particular there will be an instance for the HardForkBlock that Network will use to only convert once to this representation.

Doing this on top of karknu/tx_undecision as js/karknu/tx_undecision

[dnadales]

Eq/Ord for txid allocates: analysis and options

The problem

Eq and Ord for a Cardano transaction id allocate a fresh 32-byte array on every comparison, once per operand.
The bytes are never needed.
The id already sits in memory as four unboxed machine words that have an allocation-free Eq.

Code path

The transaction id for a Cardano block is HardForkGenTxId:

newtype instance TxId (GenTx (HardForkBlock xs)) = HardForkGenTxId { getHardForkGenTxId :: OneEraGenTxId xs }
  deriving (Eq, Ord ...)

The OneEraGenTxId instances compare the raw hash:

instance CanHardFork xs => Eq  (OneEraGenTxId xs) where (==)    = (==)    `on` oneEraGenTxIdRawHash
instance CanHardFork xs => Ord (OneEraGenTxId xs) where compare = compare `on` oneEraGenTxIdRawHash

-- defined and used only here, not exported
oneEraGenTxIdRawHash =
  hcollapse . hcmap proxySingle (K . toRawTxIdHash . unwrapGenTxId) . getOneEraGenTxId

For a Shelley-based era, toRawTxIdHash builds the bytes with hashToBytesShort:

toRawTxIdHash (ShelleyTxId i) = Hash.hashToBytesShort . SL.extractHash . SL.unTxId $ i

A Hash is PackedBytes of unboxed words, not a byte array, and hashToBytesShort allocates:

newtype Hash h a = UnsafeHashRep (PackedBytes (HashSize h))
PackedBytes32 :: {-# UNPACK #-} !Word64 -> !Word64 -> !Word64 -> !Word64 -> PackedBytes 32

hashToBytesShort = unpackBytes   -- allocates a new 32-byte ByteArray, copies the four words in

Why it allocates

PackedBytes already compares its four Word64s directly, with no allocation.
The instance bypasses that: it serialises both hashes to fresh 32-byte arrays, then compares the arrays.

compare txA txB
  ├─ oneEraGenTxIdRawHash txA → hashToBytesShort → alloc 32-byte array
  ├─ oneEraGenTxIdRawHash txB → hashToBytesShort → alloc 32-byte array
  └─ compare the two arrays

That is two allocations per comparison, plus the NS traversal, none of it retained.

Impact

Wherever these ids key a Data.Map or Data.Set, each lookup or insert runs compare about log n times, and every call allocates.
The cost scales with the number of operations and the number of peers.

• Network tx-submission. As reported in this issue, a node tracks, per peer, which txids the peer offered and which are already in its mempool, in structures keyed on txid. The same txs arrive from many peers, so the same ids are compared repeatedly. cardano-ignite profiling flagged this path, and a workaround in ouroboros-network-api removed it.
• Consensus mempool. snapshotHasTx, the snapshot's GenTxId blk -> Bool membership test, is implemented as Set.member in a Set (GenTxId blk) that snapshotFromValidTxs rebuilds with Set.fromList on every snapshot (a repeated cost tracked separately in Mempool: snapshotFromValidTxs rebuilds the GenTxId set on every snapshot #2111). The mempool also keeps a Set (GenTxId blk), and removeTxs filters against a Set.fromList of the ids to drop.
• Other consensus paths. The local tx-monitor server answers HasTx with snapshotHasTx, and the tx-submission mempool reader exposes mempoolHasTx = snapshotHasTx, rebuilding the snapshot on every network read.

Leios raises the volume of txs and ids, so the cost grows.

Already solved on the network side (independent of this fix)

Independently of this issue, ouroboros-network added a HasRawTxId typeclass (the approach proposed in the issue body) and changed tx-submission to store each txid once and refer to it by a small integer.
getRawTxId turns each id into its raw bytes once, a lookup table maps RawTxId txid to a TxKey (Int), each id is stored once, and the per-peer structures key on the Int.
Comparisons then run on RawTxId txid and Int, not on the consensus Ord, and each id is held once rather than once per peer.
Consensus branch f-f/prepare-11.1 supplies the instances, all with RawTxId = ShortByteString; per the network team, this solves the issue from their side.

This is orthogonal to the fixes below.
f-f/prepare-11.1 leaves OneEraGenTxId's Eq/Ord on oneEraGenTxIdRawHash, so the consensus paths above still allocate.
The fixes below remove that; storing each id once remains a complementary per-peer-memory win.

Fix A: cache the packed hash in the id

Javier's branch js/karknu/tx_undecision changes the raw id from bytes to the packed hash, and caches it, so comparison never builds a ShortByteString.

toRawTxIdHash returns SL.TxId (the packed hash), and for Shelley it is the identity:

toRawTxIdHash :: TxId tx -> SL.TxId       -- was: TxId tx -> ShortByteString
toRawTxIdHash (ShelleyTxId i) = i         -- Shelley instance: no work, no allocation

HardForkGenTxId becomes a product that caches the SL.TxId, computed once by txId, and Eq/Ord compare only that field:

data instance TxId (GenTx (HardForkBlock xs)) = HardForkGenTxId
  { getHardForkGenTxId  :: SL.TxId                   -- computed once, cached
  , mOldHardForkGenTxId :: Maybe (OneEraGenTxId xs)  -- era tag, kept for the wire
  }
instance Ord (TxId (GenTx (HardForkBlock xs))) where compare = compare `on` getHardForkGenTxId
instance Eq  (TxId (GenTx (HardForkBlock xs))) where (==)    = (==)    `on` getHardForkGenTxId

It is a product, not a newtype, because the id must hold two values at once: the cached SL.TxId that Eq/Ord compare, and the era-tagged OneEraGenTxId that the old wire format still needs to encode the id.
The era tag is a Maybe because the new wire version transmits only the hash, so an id decoded from it has none.

compare is then a four-word compare with no allocation, and SL.TxId is era-independent, so all Shelley eras share it.

Costs:

• it pulls a cardano-ledger type (SL.TxId) into the block-agnostic core, and forces every block's raw id to be a 32-byte Shelley SafeHash (Byron is reinterpreted with fromJust);
• the id grows: when built it stores the hash twice, plus the era tag;
• it changes the node-to-node wire format (a new version) and drops the GenTxIdByron pattern.

It's worth noting that when deployed on cardano-ignite, this branch showed a performance penalty when the old and new node-to-node versions ran side by side.

Fix B: allocation-free Eq/Ord, no new representation

Suggested by @nfrisby.
Leave the id, its representation, and the wire untouched; only replace the two instance bodies so they compare in place and allocate nothing.

Today both go through oneEraGenTxIdRawHash.
Instead, walk the NS and compare the underlying values directly:

instance CanHardFork xs => Eq (OneEraGenTxId xs) where
  OneEraGenTxId l == OneEraGenTxId r = go l r
   where
    go (Z x) (Z y) = x == y     -- same era: the era's own Eq (Shelley: SL.TxId, a word compare)
    go (S x) (S y) = go x y      -- both past the first era: descend
    go     _     _ = ...         -- different eras: compare the raw hashes

Ord is the same walk returning Ordering.
oneEraGenTxIdRawHash stays only as the oracle for a property test: the new == and compare must agree with it on all generated ids.

-- a, b :: OneEraGenTxId xs
prop_eq  a b = (a == b)    === (oneEraGenTxIdRawHash a == oneEraGenTxIdRawHash b)
prop_ord a b = compare a b === compare (oneEraGenTxIdRawHash a) (oneEraGenTxIdRawHash b)

oneEraGenTxIdRawHash compares the raw hash bytes and ignores the era, so this test fixes that semantics for the new instances: two ids with the same hash are equal even across eras, and ordering is by bytes, not by era.

The different-era branch (go _ _) is where that matters.
It must compare the hashes, not the constructor positions; ordering by position would disagree with the reference.

Caveat: comparing two ids from different eras means comparing values of two types, which needs a common representation.
With today's toRawTxIdHash :: TxId tx -> ShortByteString that representation allocates.
So either compare the packed hashes in place with a non-allocating accessor like hashToPackedBytes (it unwraps the words, no copy), or fall back to oneEraGenTxIdRawHash on this branch only: one allocation, and only when comparing ids from different eras (around a hard fork).
The same-era hot path stays allocation-free either way.

Recommendation

The network side is already handled (see above), so the open choice is how to fix the consensus side: Fix A or Fix B.

	Fix A	Fix B
blast radius	~35 files, new wire version, dropped GenTxIdByron	one module: two instance bodies + a test
ledger coupling	generic mempool interface returns SL.TxId; every block's raw id must be a 32-byte hash	none
id memory	grows (hash stored twice + era tag)	unchanged
allocation	none	none on the same-era path (rare cross-era caveat)

Advantages of B:

• It removes the consensus allocation with the smallest change: one module, no new representation, no wire change, no API break, and no cardano-ledger type in the generic interface.
• It leaves the network solution untouched and avoids the side-by-side penalty Fix A showed on cardano-ignite.

However, Fix A compares in O(1) from a cached field; Fix B re-walks the era sum (one hop per era) on each comparison.
The ouroboros-network pays this once per id (it compares the small integers it assigns, not the ids), but the consensus mempool and queries compare the ids directly, so Fix B walks the sum on every comparison there. This is CPU only, and both stay allocation-free.

Even so, Fix B is strictly cheaper than today's code, which walks the sum twice and allocates twice per comparison.
The instances use on, so oneEraGenTxIdRawHash runs on each operand:

(==) = (==) `on` oneEraGenTxIdRawHash   -- on f g x y = f (g x) (g y): runs g on x and on y

Each of those two calls walks the NS and, at the leaf, runs toRawTxIdHash, which allocates a 32-byte array:

oneEraGenTxIdRawHash =
  hcollapse . hcmap proxySingle (K . toRawTxIdHash . unwrapGenTxId) . getOneEraGenTxId

So one comparison walks the sum twice and builds two ShortByteStrings; Fix B walks once (go l r in lockstep) and builds none.

Fix A's underlying idea, a bare hash on the wire, is worth doing, but as a separate protocol change (#2110).