samchon / astl Goto Github PK

Implement those containers:

• experimental.FlatMap
• experimental.FlatMultiMap
• experimental.FlatMultiSet
• experimental.FlatSet

Through the template programming, remove similar codes in the test automation program.

As I'm a typical newbie of the AssemblyScript, I don't know whether which features are possible and which statements are not possible. Therefore, to study and be familiar with the AssemblyScript, I will implement containers and iterators first. Like TSTL, those containers would be implemented.

Linear Containers

• Vector
• List
• Deque
• ForwardList
• VectorBoolean

Associative Containers

Map Containers

• HashMap
• HashMultiMap
• TreeMap
• TreeMultiMap

Set Containers

• HashSet
• HashMultiSet
• TreeSet
• TreeMultiSet

Experimental Containers

• experimental.FlexMap
• experimental.FlexMultiMap
• experimental.FlexSet
• experimental.FlexMultiSet

Adaptor Containers

• Stack
• Queue
• PriorityQueue

Outline

Set Containers

Map Containers

Comparing elapsed time with my ASTL hash containers vs. AssemblyScript native hash containers, the AssemblyScript native hash containers are faster than of mine. Although my ASTL hash containers are based on the doubly-linked-list to providing much more features than the AssemblyScript, there're two things that can adapt from the AssemblyScript to enhance the performance.

Performance tuning

The first way is to using not the mod (%) operator but the bitwise and (&) operator in the hash buckets. If size of the hash buckets always be multiple of 2, the ^ operation can replace the % operation and it may lead my ASTL container to be about two times faster.

Modulo and Division vs Bitwise Operations

https://mziccard.me/2015/05/08/modulo-and-division-vs-bitwise-operations/

The second way is to using the manual management system of the AssemblyScript. With the @unmanaged tag who can deny automated memory management by the garbage collector like the AssemblyScript's implementation code, the performance would be enough enhanced like the AssemblyScript.

assemlyscript/std/Map.ts

https://github.com/AssemblyScript/assemblyscript/blob/master/std/assembly/map.ts

Report ternary operator bug occured in the MultiXTree.nearest_with_mover().

• Vector.Iterator<T>.operatr<()
• Vector.Iterator<T>.operatr<=()
• Vector.Iterator<T>.operatr>()
• Vector.Iterator<T>.operatr>=()
• Deque.Iterator<T>.operatr<()
• Deque.Iterator<T>.operatr<=()
• Deque.Iterator<T>.operatr>()
• Deque.Iterator<T>.operatr>=()
• MapElementVector.Iterator<Key, T>.operatr<()
• MapElementVector.Iterator<Key, T>.operatr<=()
• MapElementVector.Iterator<Key, T>.operatr>()
• MapElementVector.Iterator<Key, T>.operatr>=()

The AssemblyScript doesn't support those features yet:

• Type conjuction and disjunction
  • Therefore, it's not possible to extending the multiple interfaces
• In the closure function, capturing variables from the outside of the function scope is not possible.
• When generic extensions are composite, the compiler falls into the stack overflow
• Virtual method is not implemented yet
  • Therefore, abstract class is vulnerable

Implement those flat associative adaptor containers.

• FlatMap
• FlatMultiMap
• FlatMultiSet
• FlatSet
• LightMap
• LightSet