Make fair queue pops scale with the active origins instead of the peer count (#5252) * Benchmark the fair queue as the peer count grows nano/benchmarks/fair_queue.cpp measures a fair queue keyed by source and channel over 200 to 5000 peers, without a node: steady arrivals popped one at a time, a backlog drained in one batch, a storm with every queue full, the ready-only pop of the reply servers with a share of the channels out of room, a peer's first contact and maintenance. The channel stand-in costs what the tcp channel does, an atomic load for alive and a mutex for max, behind a virtual call. Profiles copy the caps, shares and dead origin policies of the message processor, the vote processor and the vote replier, and the queues are created in random order so the map's nodes are scattered in memory as a node's are. Every run reports time and allocations per request. allocation_counter::report takes the units of work done, for a benchmark whose iteration pops a whole batch. * Walk a ring of the non-empty queues instead of every queue on a pop A pop sought the next non-empty queue by stepping through the map of every origin, so each request cost a walk past the idle peers between the cursor and its sender: linear in the peer count, 344 ns per request at 200 peers and 17 µs at 5000 in the steady benchmark, and the same walk once per batch under load. The non-empty queues now form an intrusive ring which the cursor walks, so a pop never visits an idle origin and costs the same at 5000 peers as at 200: 109 ns per request in the steady benchmark, 2 to 20 times less on a backlog, unchanged in a storm. A queue joins the ring with its first request, just behind the cursor, which is the end of the round under way, so a round stays bounded by the queues it started with and a stream of refills cannot keep an origin with a backlog from its turn. A drained queue leaves the ring at once, and so does a dead origin's queue that the discard policy purges with its requests, the cursor moving past it as past a drained queue. Origins are served in the order they joined rather than in key order, and maintenance no longer restarts the round. Tests pin those down and cover a discarded origin wherever the round is: under the cursor at the end of its share or in the middle of it, waiting for its turn, last in the ring, every origin at once, and purged by the maintenance of a new origin or of a ready batch pop; under serve a dead origin keeps its turns until it drains. A seeded random run under both policies checks every step against a model of what each origin holds. The origin is bound by reference in next and next_ready; a copy there cost two atomic operations per pop. * Look up an origin's queue through a hash map The queues were held in a std::map, so every push paid a tree walk of log2 (peers) comparisons across scattered nodes to find its origin's queue, and the cost grew with the peer count: 109 ns per request at 200 peers and 188 ns at 5000 in the steady benchmark. The order the map kept is not needed, since the ring decides the order of service. The queues now live in a boost::unordered_node_map keyed by a hash of the source and the channel pointer. A node map keeps every entry and its key at a fixed address, which the ring hooks and the key pointers rely on. A push costs about the same at 5000 peers as at 200: 100 to 137 ns per request in the steady benchmark, 1.4 to 1.7 times less on a first contact and on maintenance. * Pop batches into a small vector instead of a deque next_batch and next_ready_batch returned a std::deque, which allocates its block map and a 4 KB block for the first element, so every bulk pop paid two allocations whatever its size, and a consumer keeping up with a trickle paid them per request. They now return fair_queue::batch, a boost::container::small_vector with room for 256 requests inline, the block processor's batch size, which a larger batch outgrows onto the heap once, reserved up front from the smaller of the limit and the queued count. The vote replier and the bootstrap server name the type as queue_type::batch, the other owners take it by auto. The alias is named only in declarations in the owners' headers and the vector is instantiated in their sources, where the request types are complete. In the steady benchmark a request costs 64 ns instead of 102 at 200 peers and 93 instead of 155 at 5000, with no allocation; a storm drains up to 1.2 times faster and a backlog is unchanged. * Serve a fair queue's origin before deciding whether its turn is over A pop asked whether the queue under the cursor had used its share before serving it. When a drained or purged queue left the ring the cursor moved on to the next queue with a count of 0, and for a share of 0 that count already read as a share used up, so that queue was passed over without a request served; behind an origin that drains and fills again on every turn it was never served at all. A share of 0 can come from pr_priority, priority_live, priority_bootstrap, priority_local and priority_coefficient, and before the ring it took one request per turn like a share of 1. pop_current now serves the queue under the cursor first and decides its turn afterwards: a drained queue leaves the ring, one that has taken its share passes the turn on, and the cursor rests on the queue whose turn it is. No check runs before a queue is served, so every queue the cursor reaches takes at least one request whatever its share, and should_seek, seek_next, seek_next_ready and after_cursor go. next_ready walks one round from the cursor's queue and leaves the round as it was when nothing is ready. Two things change in the order of service. An origin that fills while another has just used its share joins behind that origin rather than ahead of it, still served once per round. A share that maintenance lowers in the middle of a turn ends the turn one request later. That the cursor is not off the end is checked once, in pop_current, before anything is dereferenced. A queue's link state is checked in release builds where it joins and leaves the ring, since a queue linked twice or unlinked while out of the ring corrupts the list and Boost checks that in debug builds only. Tests cover a share of 0 through both pops, ready pops resuming a round and passing a turn on, clear in the middle of a round and shares refreshed by maintenance; the purge tests are reworked so the dying origin is the one the round is on, and the random test also pushes with push_evicting and holds every batch to the shares. The steady, backlog, storm, ready and first contact benchmarks measure the same as before, with no allocation added.
__________
Type: commit
Hash: 18f1a02cfee5feaeca68dda94819f2e0ccd9a5c4
Created: today
__________
gr0v1ty/nano-node:18f1a02cfee5feaeca68dda94819f2e0ccd9a5c4
| Test Case | Status | Duration | Median Deviation | Log | Graph |
|---|---|---|---|---|---|
| No test results available yet. Check the GitHub test run for job status and logs. | |||||