6 ms·

"Real-time" has a specific meaning in embedded and computing context. Does it mean that programs written in Carp have any guarantee on their order or duration o

"Real-time" has a specific meaning in embedded and computing context. Does it mean that programs written in Carp have any guarantee on their order or duration of execution?

wahern 5y ago
Unless it has a scheduler for a concurrency or threading framework, what other characteristics beyond memory management would be relevant? I guess maybe certain types of built-in data structures--you'd probably want a map/dictionary based on red-black or AVL trees rather than a hash table.
- xxs 5y ago
  Any shared datastructure needs some kind of forward gurantess; e.g. being lock-free might not be sufficient.
- KMag 5y ago
  ... or a hash table using RB/AVL trees rather than linked lists for hash buckets.
  - xxs 5y ago
    the doubling of the sizes is an issue. Yet, I'd consider all single threaded datastructures a non-issue. The hard part is multithreading. Flip note: java's hashmap uses red/black tree for nodes when there are too many collisions (and the keys are Comparable)
    - hawk_ 5y ago
      but java's hashmap still resizes when breaching the loadfactor. so any similar implementation, even for singlethreaded cases can't achieve (soft)realtime. I am not aware of any linear hashing or similar approach for in memory hash tables to mitigate such latency spikes.
      - xxs 5y ago
        of course it does; it's possible to pre-allocate the entire table though (c-tor with size, rounded to the next power of 2, compensated by the load factor). Massive waste of memory but no resizes.
xxs 5y ago
For "real-time", they would need a real-tune OS, datastructures with forward guarantees, non-blocking IO and so on. GC is like the least of the problems.
- jstimpfle 5y ago
  Not an expert at all here, just a few thoughts and experiences. I think "forward guarantees" (meaning "lock-free"?) can be implemented anywhere. Non-blocking IO can still be slow in my experience, for example a write() syscall on Linux to a non-blocking TCP socket on Linux sometimes took dozens of milliseconds when I measured. I don't have enough experience to know if one can get better timing guarantees with tuning or newer kernels, but maybe it's not a huge issue in all cases. After all, the OS is only at the outside layers of an application, so one might be able to process the OS I/O in separate threads and allocate sufficiently large buffers there. GC however, in typical usage means that random internal codepaths could be interrupted by the GC doing OS interaction in places where it's really not affordable.
  - xxs 5y ago
    lock free does not guarantee all participants have a fair treatment, e.g. one thread can keep losing the CAS (CompareAndSwap / LoadLinked/StoreConditional / etc.) and effectively spinning or need to yield. releasing the CPU resources. A non-blocking write should just copy the data to the socket buffer, definitely not taking milliseconds. Allocate buffers in separate threads - ok, that's the crux of it - the memory is shared amongst the threads within a process, so the allocator has to be non-blocking as well or the large allocation would prevent allocations in other threads. Next release memory to the OS (or unmapping memory mapped files) - mumnmap requires TLB flush for all cores assigned to the process. There is a lot that can 'block' sometimes and void the "real-time" properties. > interrupted by the GC doing OS interaction Normally GCs trigger only at 'safe points' and unless they need to allocate more memory (should never be the case for a real-time application), GCs should have no OS interaction. Copying and moving memory within a process is no OS functionality. Concurrent GC with read-barrier exist as well, so no need for stop-the-world pauses. (Edit: creative use of memory mapping hardware to avoid copying may need OS calls) It seems quite common to see on hacker news - "No GC <language> for real-time". Writing a good/multi-threaded real-time application is a lot harder than just GC's dreaded stop-the-world.

"Real-time" has a specific meaning in embedded and computing context. Does it mean that programs written in Carp have any guarantee on their order or duration of execution?

wahern 5y ago

Unless it has a scheduler for a concurrency or threading framework, what other characteristics beyond memory management would be relevant? I guess maybe certain types of built-in data structures--you'd probably want a map/dictionary based on red-black or AVL trees rather than a hash table.

xxs 5y ago
Any shared datastructure needs some kind of forward gurantess; e.g. being lock-free might not be sufficient.
KMag 5y ago
... or a hash table using RB/AVL trees rather than linked lists for hash buckets.
- xxs 5y ago
  the doubling of the sizes is an issue. Yet, I'd consider all single threaded datastructures a non-issue. The hard part is multithreading. Flip note: java's hashmap uses red/black tree for nodes when there are too many collisions (and the keys are Comparable)
  - hawk_ 5y ago
    but java's hashmap still resizes when breaching the loadfactor. so any similar implementation, even for singlethreaded cases can't achieve (soft)realtime. I am not aware of any linear hashing or similar approach for in memory hash tables to mitigate such latency spikes.
    - xxs 5y ago
      of course it does; it's possible to pre-allocate the entire table though (c-tor with size, rounded to the next power of 2, compensated by the load factor). Massive waste of memory but no resizes.

xxs 5y ago

For "real-time", they would need a real-tune OS, datastructures with forward guarantees, non-blocking IO and so on. GC is like the least of the problems.

jstimpfle 5y ago
Not an expert at all here, just a few thoughts and experiences. I think "forward guarantees" (meaning "lock-free"?) can be implemented anywhere. Non-blocking IO can still be slow in my experience, for example a write() syscall on Linux to a non-blocking TCP socket on Linux sometimes took dozens of milliseconds when I measured. I don't have enough experience to know if one can get better timing guarantees with tuning or newer kernels, but maybe it's not a huge issue in all cases. After all, the OS is only at the outside layers of an application, so one might be able to process the OS I/O in separate threads and allocate sufficiently large buffers there. GC however, in typical usage means that random internal codepaths could be interrupted by the GC doing OS interaction in places where it's really not affordable.
- xxs 5y ago
  lock free does not guarantee all participants have a fair treatment, e.g. one thread can keep losing the CAS (CompareAndSwap / LoadLinked/StoreConditional / etc.) and effectively spinning or need to yield. releasing the CPU resources. A non-blocking write should just copy the data to the socket buffer, definitely not taking milliseconds. Allocate buffers in separate threads - ok, that's the crux of it - the memory is shared amongst the threads within a process, so the allocator has to be non-blocking as well or the large allocation would prevent allocations in other threads. Next release memory to the OS (or unmapping memory mapped files) - mumnmap requires TLB flush for all cores assigned to the process. There is a lot that can 'block' sometimes and void the "real-time" properties. > interrupted by the GC doing OS interaction Normally GCs trigger only at 'safe points' and unless they need to allocate more memory (should never be the case for a real-time application), GCs should have no OS interaction. Copying and moving memory within a process is no OS functionality. Concurrent GC with read-barrier exist as well, so no need for stop-the-world pauses. (Edit: creative use of memory mapping hardware to avoid copying may need OS calls) It seems quite common to see on hacker news - "No GC <language> for real-time". Writing a good/multi-threaded real-time application is a lot harder than just GC's dreaded stop-the-world.