3 ms·

You can make bignums pretty close to the efficiency of machine words -- when storing values that fit in machine words. You do that by simply using tagged machin

by Peaker 15y ago

You can make bignums pretty close to the efficiency of machine words -- when storing values that fit in machine words. You do that by simply using tagged machine words. A few extra instructions protecting the bignum's use do not have a significant cost. In http://www.st.cs.uni-saarland.de/edu/seminare/2005/advanced-fp/docs/sweeny.pdf http://www.st.cs.uni-saarland.de/edu/seminare/2005/advanced-... Tim Sweeney says: Factoid: C# exposes more than 10 integer-like data types, none of which are those defined by (Pythagoras, 500BC). In the future, can we get integers right Neat Trick: In a machine word (size 2^n), encode an integer ±2^(n-1) or a pointer to a variable-precision integer § Thus “small” integers carry no storage cost § Additional access cost is ~5 CPU instructions But: § A natural number bounded so as to index into an active array is guaranteed to fit within the machine word size (the array is the proof of this!) and thus requires no special encoding. § Since ~80% of integers can dependently-typed to access into an array, the amortized cost is ~1 CPU instruction per integer operation. This could be a viable tradeoff.

wbhart 15y ago
In fact I've implemented precisely that first tradeoff in a library and it isn't too bad. It's still much slower than machine words though. In Dart this becomes more constrained as it uses dynamic typing. Apparently the types specified by the programmer will be thrown away when it is compiled down to VM instructions. They are only used to specify/check interfaces. What this means is that those tags become quite large in the implementation. You can try any Common Lisp or Scheme R6RS without type inference to see how fast or slow this is in practice. I don't completely understand the second trick. Where are the bignums?
- Peaker 15y ago
  He's basically saying: If the integer is tagged in its static type to be within the range of some array -- then that is proof that it is not a "bignum" and can be stored as a machine word.
  - wbhart 15y ago
    Oh yeah. That's an optimisation more languages should use. But he clearly doesn't do much mathematics if he thinks most integers are array indices. His point is doubtlessly right in his problem domain though and maybe even for a large sector of the programming community.

by Peaker 15y ago

wbhart 15y ago

In fact I've implemented precisely that first tradeoff in a library and it isn't too bad. It's still much slower than machine words though. In Dart this becomes more constrained as it uses dynamic typing. Apparently the types specified by the programmer will be thrown away when it is compiled down to VM instructions. They are only used to specify/check interfaces. What this means is that those tags become quite large in the implementation. You can try any Common Lisp or Scheme R6RS without type inference to see how fast or slow this is in practice. I don't completely understand the second trick. Where are the bignums?

Peaker 15y ago
He's basically saying: If the integer is tagged in its static type to be within the range of some array -- then that is proof that it is not a "bignum" and can be stored as a machine word.
- wbhart 15y ago
  Oh yeah. That's an optimisation more languages should use. But he clearly doesn't do much mathematics if he thinks most integers are array indices. His point is doubtlessly right in his problem domain though and maybe even for a large sector of the programming community.