Open bobeff opened 4 years ago
I think @Araq already implemented a BiTable, forgot where it was though
@Yardanico @zedeus Unfortunately this container implementation is not generic enough for the most use cases. It seems like something written specifically for a use case inside Nim's compiler.
Id
(unit32
).On a good side it is more efficient than mine which is just a thin wrapper around two HashSet
containers, because by re-implementing a hash table, it doesn't require dynamic allocation for every key/value pair with which it operates in some way.
I don't know @Araq's intentions and whether he plans to make it more generic and to put it into the standard library, but if he has such plans it can be a better alternative than my version.
(this is not an argument against a generic bitable) There are too many table (or table-like) implementations in nim repo (see https://github.com/nim-lang/RFCs/issues/200#issuecomment-597333572 and https://github.com/nim-lang/Nim/pull/13418#issuecomment-588963291) in particular the ones that are used just for the compiler.
https://github.com/nim-lang/Nim/pull/13418#issuecomment-589113619
instead of optimizing N different implementations you "optimize" a single one for diverse use cases. But this makes the problem much harder to solve, optimization is specialization. For example cellsets hashes pointers, nothing else. The only reason so much effort has to be put into the stdlib's hash tables is that we cannot anticipate how it's used.
the counterpoint of optimization is specialization
is premature optimization is the root of all evil
. We need a performance benchmark to justify the existence of compiler-specific table-like implementations; if there's at least one area where performance improves by a specialized implementation, then fine; if not, then compiler should dogfood stdlib where appropriate and the specialized implementation should be removed and performance regressions tests should be used in testament. I suspect that most compiler specific custom table implementations are not making any positive performance impact.
The compiler's hash tables have no known bugs and we can refactor them whenever we want to. Or never. I don't understand why you're pushing for this.
This RFC is stale because it has been open for 1095 days with no activity. Contribute a fix or comment on the issue, or it will be closed in 7 days.
No, we really need this.
In the standard library? Why?
In some situations there is a need for an associative container in which both types can be used as key, similar to Boost.Bimap for C++. I have such an implementation called BiTable for the project I'm working on and I'm wondering whether there is an interest for something similar in the standard library. If so and if the proposed implementation is considered good enough I will write documentation for it and I will make a pull request.
The interface is based on both
Boost.Bimap
(leftView
andrightView
procedures) and Nim's standard librarytables
module.