OSM Tags only as Tree

[droogmic]

An initial step towards a better tree structure. Generics removed for simplicity Successful tree-only data store

[droogmic]

I have gotten slighlty closer to the goals outlined in https://github.com/a-b-street/osm2lanes/issues/78, but there is still a lot to be direct. I appear to have stumbled into quite a hard problem in the get and similar interfaces for the query type Q.

• if Q is a &str, static or otherwise, we should coerce this into an iter::once
• if Q is a TagKey, we should move it in, get the parts, and drop it
• if Q is a &TagKey, we should reference the parts.

The current PR achieves the first two, but not the third, as it triggers a clone into TagKey before referencing again.

I have tried the following:

• Into/From
• Borrowed
• AsRef
• IntoIterator

I did not try Cow, even though it might work, as it makes the decision at runtime when we shouldn't need that?

Summary: I need someone who knows more than me about rust to give advice, but I think I'll need to make a toy example of the problem first.

[droogmic]

 ┌─────────┬──────────────────────────────────────────────────────────┬──────────────────┬─────────────────┬────────────┐
│ (index) │                           name                           │   baseDuration   │ changesDuration │ difference │
├─────────┼──────────────────────────────────────────────────────────┼──────────────────┼─────────────────┼────────────┤
│    0    │                    'tests/224637155'                     │ '**5.4±0.26µs**' │  '11.6±0.87µs'  │ '+1.1e+2'  │
│    1    │          'tests/380103730 Japanese Expressway'           │ '**7.1±0.35µs**' │  '13.9±0.79µs'  │   '+97'    │
│    2    │                    'tests/389654080'                     │ '**7.9±0.43µs**' │  '14.7±0.79µs'  │   '+85'    │
│    3    │         'tests/49207928 cycleway:BACKWARD=lane'          │ '**7.2±0.32µs**' │  '14.9±0.77µs'  │ '+1.1e+2'  │
│    4    │ 'tests/8591383 a bidirectional cycleway, oneway:bicycle' │ '**8.1±0.58µs**' │  '15.6±0.81µs'  │   '+93'    │
│    5    │              'tests/bus:lanes=designated|'               │ '**7.1±0.27µs**' │  '15.8±0.98µs'  │ '+1.2e+2'  │
│    6    │                   'tests/busway=lane'                    │ '**6.7±0.35µs**' │  '13.6±1.02µs'  │ '+1.0e+2'  │
│    7    │                  'tests/cycleway=lane'                   │ '**5.8±0.35µs**' │  '12.4±0.54µs'  │ '+1.1e+2'  │
│    8    │                'tests/sidewalk:right=yes'                │ '**5.3±0.25µs**' │  '11.8±0.63µs'  │ '+1.2e+2'  │
│    9    │                  'tests/sidewalk=both'                   │ '**5.6±0.32µs**' │  '12.0±0.72µs'  │ '+1.1e+2'  │
│   10    │                            ''                            │    undefined     │    undefined    │   '+NaN'   │
└─────────┴──────────────────────────────────────────────────────────┴──────────────────┴─────────────────┴────────────┘

performance has regressed across the board.

I slowed down the common path. This might be enough to justify killing the PR

[droogmic]

maybe I go the opposite direction, I remove the tree, and instead recompute it at runtime if/when needed.

There are currently very few uses of the "tree" API, basically only in bus when looking for lanes:bus:*, where we even know what the * might be...

[dabreegster]

There are currently very few uses of the "tree" API

It feels a slight bit over-engineered for the scale we've got -- 20 tags in a way would be rare. Even if we did linear search and str.starts_with, I bet performance would be OK. Way back in my comp sci undergrad, I remember using tries and I spot crates like https://crates.io/crates/qp-trie. But for so few entries, worth the complexity?

[droogmic]

indeed, let me try again.