4 ms·

Or Lisp’s approach of just using ”big” ints by default (which is practically the same but with an implicit default of “infinity”). And trust the compiler to us

by ken 7y ago

Or Lisp’s approach of just using ”big” ints by default (which is practically the same but with an implicit default of “infinity”). And trust the compiler to use fixints internally when the programmer has declared it safe to do so.

codewiz 7y ago
But that performs very poorly on all architectures.
- vzaliva 7y ago
  it does not have to. A smart compiler can narrow it down to machine size integers then possible.
  - desertrider12 7y ago
    In many situations yes, and C/C++ compilers miss a lot of opportunities for constant folding/propagation. But still, an infinitely smart compiler can’t prove anything about a value that comes from a file, user input or socket at runtime. If control flow depends on those (which is true of every useful real-life program) then you’re out of luck. GMP arbitrary-size integers are amazingly fast but still much slower than native instructions, can’t be vectorized, require heap allocation, etc.
  - klyrs 7y ago
    > A smart compiler can narrow it down to machine size integers then possible. A smart compiler will be able to narrow it down in a limited set of scenarios, but all we need to do is put an accumulator into a loop to see that bounding an integer is equivalent to the halting problem. Or for another example, should we expect our "smart" compiler to bound y in the following? The bound on x is a freebie. bigint n(uint64_t x) { bigint i = 0; bigint y = x; while (y != 1) { i++; if (y%2) y = y//2; else y = 3*y-1; } return i; }
    - klyrs 7y ago
      tfw you notice typos after the edit window closes :'(
    - vzaliva 7y ago
      As I said, "when possible". When not possible a smart compiler can give a warning or an error and ask the user to either use arbirary-precision integer or a type with bound checking.
electrograv 7y ago
I just finished writing a custom FIFO allocator for an extremely high bandwidth and low latency data processing (and UI) system written in C/C++ (even std::deque was doing WAY too many heap allocations, not to mention the allocations within each object passing through the system, despite use of move semantics to minimize redundancy). Performance improved by 100x - 1000x. And it was already blazingly fast before, if measured against performance standards we’ve become accustomed to from JavaScript and other GC languages. In high performance systems (where the benefits of C/C++/etc. outweigh the downsides), dynamic allocations always come back to bite you. If you rely on them too heavily from the start (and don’t plan for custom allocation schemes in the future), you can even get into bad situations where it’s infeasible to refactor to custom memory management (without a total rewrite), when you later need the performance gain. Incorporating even the possibility of heap allocations into a language’s most fundamental data types will doom that language to being relegated to performance-insensitive and latency-insensitive tasks, if only because it requires that a heap exist (whereas C, Rust, etc can run on embedded real-time systems with no heap). And that’s okay! It’s good that we have languages for that. But C/C++/Rust/etc. are definitely not where you can tolerate such a thing in the core language.
- ncmncm 7y ago
  If you are doing high-throughput, and you ever allocate anything after startup, you are Doing It Wrong. Any brand of FIFO loses. What you need is a big-ass ring buffer, mmapped on a hugetlbfs, fed by a process on a NOHZ isolcpu core. Readers are separate processes.
  - CoolGuySteve 7y ago
    No. Thread local/core-specific FIFO is more cache efficient than a ring buffer because the address about to be allocated is significantly more likely to be in a high level cache. With a ring buffer, you're constantly cycling out to L3 or worse and hoping the prefetcher figures out what you intend. It's basically a LIFO allocator. Even if you want to use a separate processing core, you get better latency using a FIFO allocator between 2 threads on the same core complex and the code is simpler, reducing instruction fetch overhead. Frankly, I see architectures like yours all the time from firms like Hudson River Trading and I think they suck. They incur tons of overhead, the process separation adds a useless layer of abstraction that's annoying to transcend, and you end up with this useless message protocol between cores that invokes tons of copies and breaks compiler inlining features.
cpeterso 7y ago
Here's a Go2 proposal from Rob Pike to change Go's int to an arbitrary-precision BigInt: https://github.com/golang/go/issues/19623 https://github.com/golang/go/issues/19623
tobinfricke 7y ago
The performance hit when the system has to switch from regular integers to BigInts is likely to be unacceptable in the realtime / safety-critical applications where we really care about bounds guarantees. Consider an autopilot system where the execution time massively increases when some critical value exceeds some bounds, and the system can no longer execute in the time required. In floating point systems, this is often experienced when "denormalized" numbers are encountered. In other words, it's not just guaranteed bounds on the value that is required, but bounded (and consistent) execution time.

by ken 7y ago

codewiz 7y ago

But that performs very poorly on all architectures.

vzaliva 7y ago
it does not have to. A smart compiler can narrow it down to machine size integers then possible.
- desertrider12 7y ago
  In many situations yes, and C/C++ compilers miss a lot of opportunities for constant folding/propagation. But still, an infinitely smart compiler can’t prove anything about a value that comes from a file, user input or socket at runtime. If control flow depends on those (which is true of every useful real-life program) then you’re out of luck. GMP arbitrary-size integers are amazingly fast but still much slower than native instructions, can’t be vectorized, require heap allocation, etc.
- klyrs 7y ago
  > A smart compiler can narrow it down to machine size integers then possible. A smart compiler will be able to narrow it down in a limited set of scenarios, but all we need to do is put an accumulator into a loop to see that bounding an integer is equivalent to the halting problem. Or for another example, should we expect our "smart" compiler to bound y in the following? The bound on x is a freebie. bigint n(uint64_t x) { bigint i = 0; bigint y = x; while (y != 1) { i++; if (y%2) y = y//2; else y = 3*y-1; } return i; }
  - klyrs 7y ago
    tfw you notice typos after the edit window closes :'(
  - vzaliva 7y ago
    As I said, "when possible". When not possible a smart compiler can give a warning or an error and ask the user to either use arbirary-precision integer or a type with bound checking.

electrograv 7y ago

I just finished writing a custom FIFO allocator for an extremely high bandwidth and low latency data processing (and UI) system written in C/C++ (even std::deque was doing WAY too many heap allocations, not to mention the allocations within each object passing through the system, despite use of move semantics to minimize redundancy). Performance improved by 100x - 1000x. And it was already blazingly fast before, if measured against performance standards we’ve become accustomed to from JavaScript and other GC languages. In high performance systems (where the benefits of C/C++/etc. outweigh the downsides), dynamic allocations always come back to bite you. If you rely on them too heavily from the start (and don’t plan for custom allocation schemes in the future), you can even get into bad situations where it’s infeasible to refactor to custom memory management (without a total rewrite), when you later need the performance gain. Incorporating even the possibility of heap allocations into a language’s most fundamental data types will doom that language to being relegated to performance-insensitive and latency-insensitive tasks, if only because it requires that a heap exist (whereas C, Rust, etc can run on embedded real-time systems with no heap). And that’s okay! It’s good that we have languages for that. But C/C++/Rust/etc. are definitely not where you can tolerate such a thing in the core language.

ncmncm 7y ago
If you are doing high-throughput, and you ever allocate anything after startup, you are Doing It Wrong. Any brand of FIFO loses. What you need is a big-ass ring buffer, mmapped on a hugetlbfs, fed by a process on a NOHZ isolcpu core. Readers are separate processes.
- CoolGuySteve 7y ago
  No. Thread local/core-specific FIFO is more cache efficient than a ring buffer because the address about to be allocated is significantly more likely to be in a high level cache. With a ring buffer, you're constantly cycling out to L3 or worse and hoping the prefetcher figures out what you intend. It's basically a LIFO allocator. Even if you want to use a separate processing core, you get better latency using a FIFO allocator between 2 threads on the same core complex and the code is simpler, reducing instruction fetch overhead. Frankly, I see architectures like yours all the time from firms like Hudson River Trading and I think they suck. They incur tons of overhead, the process separation adds a useless layer of abstraction that's annoying to transcend, and you end up with this useless message protocol between cores that invokes tons of copies and breaks compiler inlining features.

cpeterso 7y ago

Here's a Go2 proposal from Rob Pike to change Go's int to an arbitrary-precision BigInt: https://github.com/golang/go/issues/19623 https://github.com/golang/go/issues/19623

tobinfricke 7y ago

The performance hit when the system has to switch from regular integers to BigInts is likely to be unacceptable in the realtime / safety-critical applications where we really care about bounds guarantees. Consider an autopilot system where the execution time massively increases when some critical value exceeds some bounds, and the system can no longer execute in the time required. In floating point systems, this is often experienced when "denormalized" numbers are encountered. In other words, it's not just guaranteed bounds on the value that is required, but bounded (and consistent) execution time.