Timing Comparison of Different Rholan Type Implementations

[hilltracer]

Description

Implementations for testing of Rholang types:

1. imperative implementation (by hilltracer New rho types. Step 1 - rewrite normalizer types #34):
   Adapting of benchmark: hilltracer@b643800
2. Refactoring 1) with Eval (by nzpr and tgrospic Stack safe rho types #36)
   Adapting of benchmark: hilltracer@a17f091
3. Hash refactoring of 2) (by tgrospic Specification of hashing algorithm for Rholang AST #37)
   Adapting of benchmark: hilltracer@cd578b7
4. Append lazy to memoized Par parameters based on 3) (hilltracer@8a1c303)
   Adapting of benchmark: hilltracer@cd578b7
5. Fixing sorting in hash calculation based on 3) (hilltracer@f522f9a)
   Adapting of benchmark: hilltracer@cd578b7
6. Old protobuf implementation
   Adapting of benchmark: hilltracer@c2bbcb3

Benchmarks

For new Rholang types:
https://github.com/hilltracer/rhonix/blob/abe5f5d1a722e819bf3369318ae7d407089f59ea/rspace-bench/src/test/scala/coop/rchain/models/rholangn/ParBench.scala
For old Rholang types:
https://github.com/hilltracer/rhonix/blob/02470bee71cc89ff9cf69d0fdf5937e9c1e4fe3e/rspace-bench/src/test/scala/coop/rchain/models/rholang/ParBench.scala

Test execution commands:

sbt
project rspaceBench
# for new types
Jmh/run rholangn.SetBench 
# for old types
Jmh/run rholang.SetBench

Test conditions

• System parameters: CPU - AMD Ryzen™ 7 3700U, RAM - 16GB DDR4, SSD - M.2 PCIe 3.0x2,
• Java heap size 2048MB
• Average - 3 experiences
• WarmUp - 5 first experiences
• Data sets - Identical in all experiments

Results

Absolute values (nanoseconds)

	1) imperative	2) eval	3) hash refactoring	4) lazy params	5) hash sort fix	6) old proto
nestedAdd	30	801	795	555	505	2462
nestedCreation	132	7762	1234	256	266	1653
nestedDeserialization	798	22046	15689	12326	11866	84610
nestedEqual	12938	36646	60264	55392	53400	127352
nestedHash	6680	23933	28832	27696	27358	111603
nestedSerialization	1329	24687	29840	24060	24249	495804
nestedSerializedSize	1039	20157	22501	24582	18958	221884
nestedSort	0	0	0	0	0	600
parProcAdd	688	2357	3243	1418	1283	4564
parProcCreation	3196	256136	22751	5454	7428	60028
parProcDeserialization	5750	368286	162226	140070	125850	1860300
parProcEqual	144537	877292	1739671	1599484	1415824	4125678
parProcHash	72698	505647	905210	812671	693946	2471579
parProcSerialization	86242	758205	1044429	1126453	936897	10883799
parProcSerializedSize	11316	171095	159688	155002	132452	5671441
parProcSort	0	0	0	0	0	588
manyAppends	15029	281207	49189	29093	26935	56772

Relative values (times relative to the 1) implementation)

	1) imperative	2) eval	3) hash refactoring	4) lazy params	6) hash sort fix	5) old proto
nestedAdd	1	26.64	26.44	18.47	16.79	81.89
nestedCreation	1	58.80	9.34	1.94	2.02	12.52
nestedDeserialization	1	27.61	19.65	15.44	14.86	105.98
nestedEqual	1	2.83	4.66	4.28	4.13	9.84
nestedHash	1	3.58	4.32	4.15	4.10	16.71
nestedSerialization	1	18.58	22.46	18.11	18.25	373.11
nestedSerializedSize	1	19.41	21.66	23.67	18.25	213.61
nestedSort	1	1.00	1.00	1.00	1.00	?
parProcAdd	1	3.43	4.71	2.06	1.87	6.63
parProcCreation	1	80.13	7.12	1.71	2.32	18.78
parProcDeserialization	1	64.05	28.21	24.36	21.89	323.54
parProcEqual	1	6.07	12.04	11.07	9.80	28.54
parProcHash	1	6.96	12.45	11.18	9.55	34.00
parProcSerialization	1	8.79	12.11	13.06	10.86	126.20
parProcSerializedSize	1	15.12	14.11	13.70	11.70	501.17
parProcSort	1	1.00	1.00	1.00	1.00	?
manyAppends	1	18.71	3.27	1.94	1.79	3.78

Descryption of tests

Nested par

Par = List( List ( List (…))) (100 level nested Par)
nestedCreation - creation of Par
nestedAdd - combining this Par with Int(0): Par | Int(0)
nestedDeserialization - create this Par from bytes
nestedEqual - equal this Par with another
nestedHash - calculate hash for this Par
nestedSerialization - convert this Par to bytes
nestedSerializedSize - calculate serialized size of this par
nestedSort - sorting Par elements. Needs only for old types, because integrated into hashing and serialization in new types

Flatted par

Par = List(…) | List(…) | List(…) | List(…) | … (100 elements)
parProcCreation - creation of Par
parProcAdd - combining this Par with Int(0): Par | Int(0)
parProcDeserialization - create this Par from bytes
parProcEqual - equal this Par with another same Par
parProcHash - calculate hash for this Par
parProcSerialization - convert this Par to bytes
parProcSerializedSize - calculate serialized size of this par
parProcSort - sorting Par elements. Needs only for old types, because integrated into hashing and serialization in new types

Sequential combining

manyAppends - Combining 100 Pars with each other using the fold function List(…) | List(…) | …

Acceleration of reducer

In order to evaluate how a simple replacement of types in the current reducer will affect the speed of Rholang, you can be guided by the document rchain#3743

For example: to one produce old reducer required: 4 serialization (There is an error, in fact, the size is calculated 3 times and only 1 time is serialized) + 1 hashing + 1 sorting. But the most slowest thing is serialization.

In new types the size of the serialized data calculates only ones and next preserved in types and do not needed to be calculated 4 times. Thus, estimates show that for only one serialization, when replacing old types with new ones, we will have an acceleration of about 500 * 4 times (for implementation 1)), or 33*4 times (for implementation 3). This data is only for simple types, for collections (map or set), we will get even more speedup

Сonclusions

• The new types are significantly faster than the old types, and estimates show, that simply replacing the old types with the new ones without refactoring will speed up Rholang a lot.
• The introduction of the Eval monad to protect the stack slows down processing dozens of times, but this is acceptable for this stage, because even with such parameters we should get a speedup.
• Refactoring (hash fixing - implementation 3) сauses an additional loss of hash processing speed by 2 times, compared with a simple Eval calculation (implementation 2) for multiElement pars (see parProcHash).
• We can improve performance if we make lazy parameters, and not rely on memoization in Eval. As here: hilltracer@0e45cdb
• We can improve performance if we will use already sorted data during hash calculation. As here: hilltracer@0e45cdb
• In the future, to speed up types, we can rewrite Eval processing and introduce manual tail recursion, which should give a speedup of 10 times.