[MDSAL-80] Lack of default comparator Created: 21/Apr/15 Updated: 09/Mar/18 Resolved: 27/Oct/16 |
|
| Status: | Resolved |
| Project: | mdsal |
| Component/s: | None |
| Affects Version/s: | None |
| Fix Version/s: | None |
| Type: | Improvement | ||
| Reporter: | Anton Ivanov | Assignee: | Unassigned |
| Resolution: | Won't Do | Votes: | 0 |
| Labels: | None | ||
| Remaining Estimate: | Not Specified | ||
| Time Spent: | Not Specified | ||
| Original Estimate: | Not Specified | ||
| Environment: |
Operating System: All |
||
| Description |
|
Presently, the only code generated by yangtools for objects is equals(). This limits the possible scalable lookup methods for storing large number of objects to HashMap() and derivatives. There is a number of key areas where hashmap is known to be the wrong answer - v4 prefixes and routing tables, large numbers of tunnels, etc. These are better services by a variety of a Tree (f.e. B tree). Trees require a comparator which returns less, equal, more in order to be implemented. This is missing. Proposal: In addition to the current equals() to have a compare() method which by default returns the lexical compare of the string representation. If overrides and optimizations are implemented (f.e. for prefixes and ip addresses), more appropriate comparators can be implemented. Example - taking the prefix length into account when comparing prefixes so they can be arranged into a tree for a fast longest prefix match. |
| Comments |
| Comment by Robert Varga [ 27/Oct/16 ] |
|
Unless I am missing something, this can easily be addressed externally by supplying a specific Comparator for the collection in which the object is being stored. |
| Comment by Anton Ivanov [ 27/Oct/16 ] |
|
(In reply to Robert Varga from comment #1) A Collection a B-tree does not make and all high performance algos for working with large routing tables, etc are tree/radix based. They are not based on sorted collection and only "intro level" ones are based on maps/hashmaps. If there is no comparator you cannot implement these in a standardized fashion so it can be reused, each implementation has to be bespoke. A. |
| Comment by Robert Varga [ 27/Oct/16 ] |
|
This is pretty much a question of how you integrate into a particular data structure. We simply cannot provide all of that integration unless there is a well-described common pattern and if a different structure, requiring different type of integration occurs, we will end up going back to basics. In your line of argumentation it is impossible to store objects which do not implement java.util.Comparable in a java.util.TreeMap. Except it is, as you can provide a java.util.Comparator at TreeMap instantiation time, which the implementation will consult to understand how the object being inserted/looked up compares to other objects. The same design pattern should be followed when integrating with external data structures. |