...
From the cost accounting perspective, reduction of the rholang program is one of the following:
1. Evaluating a term.
2. Substituting variables in the term.
3. Spatial match algorithm.
4. Methods called on rholang terms.
5. Interaction with RSpace.
Evaluating a term
TODOWe charge constant cost for evaluating a term like: send, receive, method call, variable. This is a constant cost for which order is the same as basic methods like nth method call, keys etc.
Substitution
Substitution is the process where we substitute bound variables with the environment variables they bind to. This process can either succeed or fail (failing to substitute is an error but we charge nevertheless). The cost of substitution is:
- for success cost proportional to the byte size of the substitute term
- for failure cost proportional to the byte size of the original term
...
so the more (term, pattern) comparisons match requires the more expensive it is. The actual cost of comparing term against pattern is proportional to the byte size of the smaller object. This is based on the java equality method.
Methods
| nth | toByteArray | hexToBytes | toUtf8Bytes | union | diff | add | delete | contains | get | getOrElse | set | keys | size | length | slice | append | interpolate | |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| List | C | -- | n/a | n/a | n/a | n/a | n/a | n/a | n/a | n/a | n/a | n/a | n/a | n/a | C | proportional to value of higher index | proportional to the length of underlying string | n/a |
| GByteArray | n/a | n/a | n/a | n/a | n/a | n/a | n/a | n/a | na | n/a | n/a | n/a | n/a | n/a | n/a | proportional to value of higher index | proportional to the logarithm of length of target byte array | n/a |
| Tuple | C | -- | n/a | n/a | n/a | n/a | n/a | n/a | n/a | n/a | n/a | n/a | n/a | n/a | n/a | n/a | n/a | n/a |
| Set | n/a | -- | n/a | n/a | proportional to the size of collection that is an argument method | proportional to the size of collection that is an argument method | C | C | C | n/a | n/a | n/a | n/a | proportional to the size of base collection on which this method is called. Complexity of the size method is O(n) | n/a | n/a | same as union | n/a |
| Map | n/a | -- | n/a | n/a | proportional to the size of collection that is an argument method | proportional to the size of collection that is an argument method | n/a | C | C | C | C | C | C | proportional to the size of base collection on which this method is called. Complexity of the size method is O(n) | n/a | n/a | same as union | n/a |
| any term | n/a | proportional to the byte size of the underlying rholang term | n/a | n/a | n/a | n/a | n/a | n/a | n/a | n/a | n/a | n/a | n/a | n/a | n/a | n/a | n/a | n/a |
| String | n/a | -- | proportional to the length of underlying string | proportional to the length of underlying string | n/a | n/a | n/a | n/a | n/a | n/a | n/a | n/a | n/a | n/a | C | proportional to value of higher index | proportional to the sum of the lengths of both strings | proportional to length_of_string * number_of_entries_in_map |
- C - constant
- n/a - method not available
...