mapbox / mapbox/vtzero

Indexes for key/value tables in layers

Open
#30 2 comments 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

Dominant language
C++
Stars
106
Forks
29
PR merge metrics
No merged PRs in 30d

Description

*This issue documents the current state of affairs concerning indexes for key/value tables. Other issues can refer back to this for context.*

When building a new layer you need to populate the key/value tables while adding new properties. There are several ways of doing this:

1. Use the builtin index. This is the easiest choice, but performance isn't great. It uses a flat vector with linear search for small numbers of entries or an `std::unordered_map` when there are more. Some quick benchmarks show that the [current value of 20 entries beyond which the implementation switches to `std::unordered_map` is reasonable](https://github.com/mapbox/vtzero/blob/master/include/vtzero/builder_impl.hpp#L81).
2. Use the [`property_mapper`](https://github.com/mapbox/vtzero/blob/master/doc/advanced.md#using-the-property_mapper-class-when-copying-layers). This is the best choice when copying some features (or some properties of some features) from one existing layer, it is more than twice as fast as the builtin index.
3. Use one of the supplied indexes in [`index.hpp`](https://github.com/mapbox/vtzero/blob/master/include/vtzero/index.hpp).
4. Do everything yourself. You know the data best that you are adding and can choose the right strategy.

Medium term we should think about a better implementation for (1), but this needs more benchmarks with real data and different implementations to find the best one. Because this is hidden from the user of the library, we can always improve on this later.

It is unlikely that we'll find a much better approach for (2) than the current one. But this is only usable in very specific circumstances.

We can always add to (3), for instance adding vector-based flat maps with linear search.

Contributor guide

Open the contributing guide

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

Research direction

Read include/vtzero/builder_impl.hpp for the builtin index, doc/advanced.md for property_mapper, and include/vtzero/index.hpp for supplied indexes. Benchmarking with real data and deciding whether to improve the builtin implementation or add vector-based flat maps is still an open design task, so the issue does not define a specific done state.

Written by the indexing model from the issue text.

Assessment

Tech stack
cpp
Domain
performance
Issue type
Feature
Difficulty
5/5
Estimated time
Over a week
Activity status
Stale
Clarity
Needs clarification
Newbie friendliness
25/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.