Various optimization ideas

[tafia]

This PR is not necessarily meant to be merged as is, it is rather several optimization ideas for the lru_cache.

• LruCache:
  • use an Option<Duration> for time_to_live in order to make the intent clearer than using a static Duration value
  • use a Vec instead of a VecDeque because we always push_back and pop_front => push and drain works well enough I think. Not sure for this one ...
  • in general avoid searching in the map twice (one for expired fn and one for actually getting the value)
• iterators (Iter and PeekIter):
  • use lru_cache_ttl for PeekIter so it reflects Iter logic better
  • match lru_cache_iter only once per iteration
  • replace while let with simpler find and remove the clippy cfg

I couldn't install rustfmt-nightly 0.8.2, so I expect some breaks, I'll fix them later.

[maidsafe-highfive]

Thanks for the pull request, and welcome! The MaidSafe team is excited to review your changes, and you should hear from @Fraser999 (or someone else) soon.

If any changes to this PR are deemed necessary, please add them as extra commits. This ensures that the reviewer can see what has changed since they last reviewed the code. The way GitHub handles out-of-date commits, this should also make it reasonably obvious what issues have or haven't been addressed. Large or tricky changes may require several passes of review and changes.

Please see CONTRIBUTOR.md for more information.

[tafia]

Also, any reason to use a BTreeMap instead of a HashMap (which could probably be faster?). I understand that it requires the Key to be PartialEq + Hash instead of just Ord, but this doesn't really looks like an issue in practice.

[Fraser999]

Also, any reason to use a BTreeMap instead of a HashMap (which could probably be faster?). I understand that it requires the Key to be PartialEq + Hash instead of just Ord, but this doesn't really looks like an issue in practice.

That's down to our requirement to have reproducible tests in our crates which depend on this one. If we use a HashMap we lose the ability to rerun a failing test with a given RNG seed and get the same failure repeatedly.

This requirement may change in the future, or we may want a solution where we use a container which is optimised (like HashMap) for production use, but can be made deterministic via a feature for the case of reproducible tests. Not sure how that'll pan out, but we've largely been focused on code correctness for now, with optimisations taking a back seat at the moment.

[tafia]

Thanks for the review both of you. I had to leave yesterday so I couldn't answer you.

• I have kept the Vec because I don't think the draining iterator is so bad compared to pop_front. This could be revisited After a quick benchmark between the 2, I think it is indeed better to keep the VecDeque. I have reverted it.
• I have revert to counting the expired items for len (and checking only the last one for is_empty). I have added a FIXME comment as well so this could be improved with some mechanism if someone is having an issue. For the time being, you are the primary users of this crate so it is better to address your concerns first.
• for the HashMap vs BTreeMap, indeed it could probably be a feature ... I think the performance penalty shouldn't be too big, on the other hand it is not following the least astonishment principle. Again, you are the primary users so better to let it this way for now.

[pierrechevalier83]

Thanks for this new contribution, @tafia :smile: