[c-lightning] Shared-memory Routemap

[Rusty Russell]

ZmnSCPxj <ZmnSCPxj at protonmail.com> writes:
> Hi all,
>
> Rusty expressed the opinion, to move routing techniques to plugins.
> And he made also https://github.com/ElementsProject/lightning/pull/3075 .
>
> Simply put, the consideration of this pull request is to reduce representation of nodes and channels, so contains fields only for purpose of routemaps.
> And each plugin separately reads the `gossip_store` file to create an in-memory routemap.
>
> My concern, is that this routemap is (to my mind, needlessly) duplicated across each plugin instance.
> Consider that we may eventually have a `getroutequick` and `permuteroute` and `recalcroute` implementat1ions (as well as legacy `getroute` implementation), possibly in separate plugins for easier code management.

Well, each node needs to generate its own index (mapping scids to
offset, and nodeids to offsets).  But that makes sense, since they may
have different needs, and the index is only 10MB currently.

I checked with the million-channels-project: it's still only 72MB for
the indices.  And it takes about 2.3 seconds to load (vs 200msec for the
current gossip store) on my laptop.

> Synchronization
> ===============
>
> As the memory is shared, we should take care the synchronization across multiple threads-of-control.
> Thus, we should care point, to use a proper synchronization structure.

You've reinvented one of my favorite projects: libantithread :)

But it's overkill for the moment, and complex and fragile, as you
describe.  Using a database for the indexes might be a halfway model
(either sqlite3 or tdb), but it's simply not worth it.

I've done some bugfixes, and here are the current numbers for my laptop
and my rPi:

The result is that the current gossip_store:
 - load time (-O3 -flto laptop): 90msec
 - load time (-O3 rPi): outlier 3110msec, mean 500msec
 - Total memory: 7.0MB:
   - 3.8MB for the array of channels
   - 2.0MB for the channel htable to map scid -> channel.
   - 460k for the array of nodes
   - 510k for the node htable to map nodeid -> node.
   - 245k for the array of channels inside each node

For the million-channels-project (~780MB of gossip):
 - load time (-O3 -flto laptop): 1153msec
 - load time (-O3 rPi): outlier 50,000msec, mean 35,000 msec
 - Total memory: 67.4MB:
   - 39.7MB for the array of channels
   - 16.0MB for the channel htable to map scid -> channel.
   - 2.4MB for the array of nodes
   - 2.0MB for the node htable to map nodeid -> node.
   - 7.3MB for the array of channels inside each node

Cheers,
Rusty.