Friendship ended with the garbage collector
yorickpeterse.com
yorickpeterse.com
Just like .net allows you to use "unsafe". It is a clear marker that you are stepping outside of the safe zone and need to be careful, but at least you can.
But this means that the programmer suddenly needs to actively think about memory management (and already in the design/planning phase, because later is too late), while the whole selling point of automatic memory management solutions was that this wouldn't be necessary anymore (which was a deception all along, but that's a different topic).
Or allocating on the stack (just mind the size of the allocation and the current depth of the stack). Common Lisp offers the DYNAMIC-EXTENT declaration for that: http://www.ai.mit.edu/projects/iiip/doc/CommonLISP/HyperSpec...
edit: scooped by a sibling comment! :) ah well, here's what you could use to structure objects in a numpy array https://numpy.org/doc/stable/user/basics.rec.html?highlight=...
Those shops aren't going to use ZGC.
Nor they will profit from the several performance improvements, including the free JIT cache across runs with PGO data on Hotspot and J9, that used to be a commercial feature on third party JDKs.
D is designed exactly like that. In fact, using value types and smart pointers (using `typecons`) is kind of required if you want to keep GC pauses tolerable. On the flipside, a simple GC means no additional overheads like write barriers or remembered sets. Additionally, a borrow checker for D has also been in development (I have not personally checked it out to comment on it though).
Intended use is to use value types for small immutable values (small because copying large objects is more costly, and immutable so that the copying doesn’t make a difference, semantically)
That can significantly decrease the number of garbage collected objects and with it memory usage (the smaller the object, the larger the relative overhead of a few bytes of data for use by the garbage collector)
Have a look at D, Active Oberon, Modula-3, C#, F#, VB (6 and .NET), many BASIC dialects, Eiffel, Haskell (now with experimental lifetimes), Swift (RC is a GC algorithm), C++/CLI, C++/CX, Unreal C++, Common Lisp, among many others.
The big problem is a big lack of quality when teaching CS subjects, so many learn GC and think all GC languages are like JavaScript.
Obviously this is a bit more difficult than say Java, but then you never have to stop the world.
The only thing it does is to automate the retain/release calls of Cocoa classes, or classes that offer similar API.
It doesn't apply to any other C like types from Objective-C, and basically the generated machine code is hardly different than when devs keep doing those calls by hand.
Yes there is some potential for the compiler to remove needless set of retain/release pairs for short lived objects, it doesn't happen all the time though.
Swift, also despite the ARC marketing, made the sensible choice to go with ARC, because one of the key designs was interoperability with Objective-C runtime.
As shown by RCW/CCW runtime used by .NET for interoperability with COM's AddRef/Release, there is a lot of more machinery required to have a tracing GC cooperate with RC scheme, so it was understandable this route wasn't chosen for Swift.
As some papers prove, current performance isn't that great, which is also Swift 5.5 is bringing a more aggressive optimization, which is turned off by default.
Check WWDC 2021, "ARC in Swift: Basics and beyond".
I wonder if this could be also handled by having a custom error handler available on each created reference, to decide what to do with the "hanging" value, whether to reassign ownership, or invalidate the reference, or panic, or do whatever else.
"When the reference goes out of scope, the count is reduced. When an owned value goes out of scope and its reference count is not zero, the program terminates with an error (which I'll refer to as a "panic")."
At the end of the day, in a general purpose language, it's great to have machinery to avoid needing GC when possible, but you really do want to have GC to fall back on.
This is not true. The counter itself can have its count updated atomically with a compare & exchange. I think this is what actually happens in most cpp std libs, but haven't checked in a while. (This doesn't mean the object they point to is thread safe though!)
But here's my question: Why do C++ programmers always refer to the overhead of "reference counting", when the overhead is not in the counting, but in the memory management: the use of doug lea's malloc or its derivatives such as ptmalloc3. This is what "new" wraps, and the STL objects all use it to resize themselves too. These routines are written by geniuses, but if you actually read up on how they work, they are doing a lot of (completely necessary) stuff, and one of the longest-running std lib calls you can make. (Way longer than an exp(), for example).
Presumably they're looking at reference counting as an alternative to unique_ptr, and in that context the memory management overhead is already being paid.
I have been under the impression that glibc implements both unique_ptr and shared_ptr (that's the one with arbitrary refcounts) using locks, but ok, if it's done with something like CMPXCHG that's still a heck of a lot slower than ordinary copying.
As for overhead, well, if an object lives for a long time and lots of references are updated or moved around, then that itself can be expensive, besides the malloc/free costs. Copying garbage collectors by comparison are simple and fast, at the expense of making your program gobble a lot more memory, limiting the language so that the gc can know where all the pointers are, and having to stop the program during gc.
Why would unique_ptr ever need a lock?
> As for overhead, well, if an object lives for a long time and lots of references are updated or moved around
If performance is important you only pass a shared_ptr if the callee needs to keep it around, otherwise just pass a plain (const) reference. You can also pass a (const) reference to the shared_ptr and then the callee can decide if they actually need to keep it. Moving shared_ptr is free, because the refcount stays the same.
But I agree that GC has higher thruput than malloc/free as most gc allocations are a single op, at the cost of higher initial memory usage and worst-case latency. That's why "scripting" languages like python / perl use refcounting as they need to start quickly and might not run for very long, whereas java / c# programs tend to be longer running.
eh, not that much.
use.cpp:
double rand_double() { return 16.; }
int rand_int() { return 16; }
void use(void*) { }
#include <iostream>
#include <chrono>
void run();
int main()
{
auto t0 = std::chrono::high_resolution_clock::now();
for(int i = 0; i < 10000000; i++) {
run();
}
auto t1 = std::chrono::high_resolution_clock::now();
std::cout << std::chrono::duration_cast<std::chrono::milliseconds>(t1 - t0).count() << std::endl;
}
#include <cstdlib>
int rand_int();
void use(void*);
void run()
{
auto res = malloc(rand_int());
use(res);
free(res);
}
#include <cmath>
double rand_double();
void use(void*);
void run()
{
auto res = exp(rand_double());
use(&res);
}
double rand_double() { return 16.; }
int rand_int() { return 16; }
Not only that, but the original doug lea's malloc has a bin specifically for 16 byte allocations: http://gee.cs.oswego.edu/dl/html/malloc.html (the smallest size), so you've specifically chosen a very fast example.
In order to properly test malloc() you have to pre-generate some pseudo random numbers for your allocation sizes, and allocate and free unpredictably. But it's more complicated than that, as in the very occasional case when malloc() has to ask the OS for more heap, that system call may not "finish" until your program first writes to that region of memory... (ie malloc() returns but hasn't finished!)
I agree that malloc/new is comparatively expensive, but that ends up as a cost borne by all heap-allocated variables in every language. Unless people use special techniques like pool or slab allocators.
The real gains of managing memory manually is not in the speed of malloc(), but in the fact that in practice you can perform far fewer heap allocations.
At some point you have to consider how that hardware implements atomic variables and cmpxchg, because it is certainly not free.
You’re mistaken. In a multi core or multi processor system, atomic operations necessary for shared RC are relatively expensive. Heap allocation cost is paid for any dynamic object no matter the type of GC/RC used, so that is not what is being compared.
Moving objects between processes itself doesn't lead to fragmentation, as processes don't have their own heap in the data structure sense. That is, the structures representing a process don't have some sort of "heap" field. Instead, the OS threads running processes maintain the heaps (each thread has its own heap). This brings several benefits:
1. Since the heap is physically detached from processes, we can move without copying
2. Since the heap is still thread-local, allocations don't need synchronisation
3. Since the heap is detached from the processes, each process is smaller, allowing for more processes to run concurrently
4. Since objects (and their children) can only be owned by one process, we also don't have to worry about multiple processes trying to write into the same object
This is only possible because we statically guarantee that a value `T` can't be _shared_ between processes, and because we'll disallow sending references between processes.
https://gist.github.com/matey-jack/3e19b6370c6f7036a9119b79a...
In fact, the Rust book explicitly mentions doubly linked lists when discussing Pin:
https://doc.rust-lang.org/std/pin/index.html#example-intrusi...
The ownership system might make it less trivial to implement, but the statement that you cannot implement it in safe Rust is incorrect regardless.
That said, i'd still prefer a simple Reference Counting than a full GC as it's quite memory hungry and collections introduce pauses.. wich is not a desirable behavior at all, even though pauses can be solved, i'm no a fan of the idea that a language manage my memory in unpredictable ways
The reason i use D is because i can use it just like C/C++ (with modern niceties such as module, slices, metaprogramming and fast compile time) with my own allocators, completely ignoring the GC
But whenever i need a quick and dirty "script" (it almost never happen), instead of using bash or python, well i simply just use D with its GC, but again, as i said above, i'd prefer a simple RC instead.. but yeah.. it's no big deal since i prefer to manage memory my way anyways
A perfect language understands your intent without impacting your workflow with slow compile time due to heavy, restrictive and slow compile time static analysis (borrow checker for example)
So web servers benefit from arena allocation
GUIs benefit from ARC
Short running programs can benefit a lot from just leaking memory.
I guess Process does not refer to an OS Process here?
It was reference counting in the 80s and 90s. And then tracing GC people stepped in. "Reference counting is worse of both worlds. It's slower than GC because all these memory have to be touched!"
But real life experience continues to show ref counting doing better. And GC users pre allocating object pool to avoid GC pauses. Proponents still in denial. "What if a large object is deleted? That will also create GC pause like delay."
And now here we stand. Back to reference counting.
That languages get popular is no surprise. But what was a little bit surprising for me was that the tech the language uses gets spread and popular all over -- outside of that language as long as that language stays popular.
I right now am think automatic reference counting is the way to go. In a sense C++ RAII is also ARC. But a compiler level support is better.
"Garbage collecting", so, you mean, you're leaving garbage around then? Why?
With RC you're acting on the deallocation as soon as you are allowed to. Sure, you don't need to actually deallocate at that time, but you're acting upon it.
"Oh but what about loops" well, you can work around those (and they are rare).
My point is not that GCs are not useful. My point is that there is a better way of dealing with allocations if you know your object is not used anymore and not just treating memory as infinite.
And despite what some people think, malloc/free are not O(1) free lunch.
> And despite what some people think, malloc/free are not O(1) free lunch
Of course. Be it through a GC allocator or not. If you're at the point where the allocator is giving you trouble then GC/RC is the least of your problems ;)
If you want to talk determinism, you need to actually invest into deterministic behaviour - something that either requires dropping dynamic memory allocation altogether, or tends to go for GC with known determinism guarantees (for example, IBM Metronome).
The problem with rc is not memory access but synchronization.
So it's hard to make alternative implementations that don't die.
If you want more information about this topic, there is a nice talk by Larry Hastings: https://www.youtube.com/watch?v=pLqv11ScGsQ
RC speed is not even close to the reason Python doesn't have proper multithreading.
(The GIL, and API/ABI guarantees to third party C-based extensions making it difficult to remove it, is more like it. The GIL was added to aid in RC atomicity - but it's not the speed of RC that's the issue).
Actually, I've heard that Go sacrificed speed big time to minimise its pauses. Garbage collectors generally face a latency/throughput tradeoff, and I believe Go is no exception.
That said, fast GC with reasonable pauses existed long before Go. I personally know of OCaml and its generational, incremental GC. I expect Go built on that knowledge to find its own sweet spot.
Hmm... not in my experience at least, for instance Apple's ARC (which should be much better than "dumb" shared_ptr refcounting because the compiler does some static analysis and drops redundant retain/release operations) still can have a shockingly high runtime overhead and requires careful manual tweaking and general handholding to the point where the traditional manual memory management results in simpler code, at least in hot code paths.
Now GCs may well be worse, but performance-wise they really can't be much worse than ARC. ARC may sometimes prevent unpredictable GC spikes, but only by spreading out the same (or worse) cost along the timeline (which is at least something, but many GCs simply haven't been designed for the "prevent spikes" requirement).
There simply is no silver bullet for dynamic memory management, at least if both memory usage and performance matters.
What experiences would be that? "GC pauses" exist in stop-the-world garbage collector's phase. If you need a concurrent one - they exist just as well.
https://github.com/ixy-languages/ixy-languages
https://forums.swift.org/t/swift-performance/28776
It is no wonder that Swift 5.5 brings aggressive compiler optimisations that can even break code that naively relies on basic ARC behaviour.
RC also has pauses, pretty lengthy ones with cascade deletions, and can even lead to stack overflows.
"CppCon 2016: Herb Sutter “Leak-Freedom in C++... By Default""
Which is why as GC algorithm reference counting is only for toy implementations.
Any reference counting implementation that cares about performance in multicore environments is almost indistinguishable from a tracing GC implementation.
In fact, C++/WinRT, uses background threads to diminish the performance impact of calling destructor and cascading deletions.
https://devblogs.microsoft.com/oldnewthing/20191018-00/?p=10...
But you can find on net whatever you seek, whatever you are looking for.
> Which is why as GC algorithm reference counting is only for toy implementations.
That's what I heard from last decade. And then experience has outgrown likes or dislikes.
The fact that Swift and Objective-C get outperformed in any research about automatic memory management is quite real, not urban myths.
This may be correct for doubly linked lists in the classical implementation, but I've never needed one outside of programming exercises. Trees can be safely implemented in at least 2 ways. Rust is limiting, but usually more in terms of approach, not possibilities. As long as the program isn't interacting with the "unsafe" outside environment it's usually no problem avoiding unsafe blocks completely.
https://0xax.gitbooks.io/linux-insides/content/DataStructure...
Edit: Not that I know much about the Linux kernel, but I do remember it being used as a counter example when someone stated before that nobody uses doubly-linked lists.
Its as much work to use a garbage collector efficiently as it is to allocate and delete your own memory. And with about the same bugs. It's been problematic from the start.
Not a fan of automatic systems to 'manage' memory. Overhead for automatic systems create lag, latency and bloat. I'm old-fashioned, and create code that has strict ownership of allocated memory by subsystem. If a module that allocates also frees, leaks become negligible. If references are not shared but accessed formally, nulls become returned errors etc.
Discipline is hard, but leaky buggy garbage-collecting behemoths are hard to live with too.
Seamless interop with C, even when cross compiling which Zig handles natively: the standard install of Zig comes with a "zig cc" wrapper around clang that allows you to cross compile[2][3] C and zig code for any number of target architectures (it includes C standard library headers and code for them).
Zig is the only language I've come across which functions perfectly as a better C.
[1]: https://ziglang.org
[2]: https://actually.fyi/posts/zig-makes-rust-cross-compilation-...
[3]: https://andrewkelley.me/post/zig-cc-powerful-drop-in-replace...
Most of the time (in my practice, like 99% of the time) you don't have to care about nulling references. The objects that need collection are created in local scopes of functions, and get detached and ready for GC right when the function returns. When you have many small functions, this happens often, so unused objects don't spend much time being referenced and ineligible for GC.
The problematic part is long-living mutable structures, which you hopefully have few, and know well where they are in your code.
Also, as an exercise, I suggest that you try to imagine a Lisp with explicit memory management.
Remembering to null references is not much easier than remembering to delete things. It's trading one issue for another.
And now there's two ways to remember to manage memory.
There are exceptions to that, like queues and caches, but they are few and should be closely watched.
I already write web services in Rust. It's no more difficult than Java or Python.
I can't wait for the ecosystem to heat up more, because it'll make it compelling to switch to Rust at work.
But if you care enough to be writing tests or put lots of thought into API and schema, then maybe you're in the disciplined camp that would get a ton of benefit from switching.
If you're using C++, you should switch for any greenfield project that doesn't need to use legacy libraries. (Writing wrappers for C libraries isn't hard at all.)
Typically I just use weak references or weak reference sets/dicts/whatever. That's python for you though.
I presume you mean it's just as hard in some specific language, not just as hard in general.
How to avoid it? Think. Be careful. Write good test suites. Run them a lot. It really isn't so hard.
This mindset lead to countless security problems and other bugs in all kinds of software. Even now we still find exploits in sudo and openSSL. And the problem wasn't developers leaning back and saying "today I'm going to program carelessly and do a bad job because why the hell not".
GC was also originally developed for LISP; I'm not sure it's even conceptually possible to have a manually-manged lisp, although I think there's a refcount implementation somewhere.
Many tend to mix the choice of implementation language, with other criteria that the authors cared more about.
That is after all how Lisp workstations like Interlisp-D or Lisp Machines were implemented, and those features carried on into Common Lisp.
Could it be that you never shed the bias from your young 80s BASIC experience, despite the world around you changing?
Concurrency is a much harder problem and something we deal with more often. I would consider memory management close to not a concern.
Absolutely. The longest lasting bug I've ever had was in some multi-threaded code in a trading server (and nothing to do with memory - shared resources getting corrupted). When I tracked it down (after about 6 months!) I repeatedly banged my head on my desk, yelling "You idiot, you idiot, you idiot!" - referring to me.
Compared to stuff like this memory leaks are really easy to test for, detect, and fix. Anyone can write a test harness to see if there is a leak.
This doesn't align with the continuing serious security problems associated with memory-management bugs.
> The Chromium project finds that around 70% of our serious security bugs are memory safety problems.
https://www.chromium.org/Home/chromium-security/memory-safet...