Bad code? As in *really* bad?

wharrgarbl

@Bulb said in Bad code? As in *really* bad?:

C has exactly the right building blocks. It should have a library on top of them though.

A decent string variable type should grow and get freed automatically when out of scope, that requires at least something like destructors.

RaceProUK

@wharrgarbl said in Bad code? As in *really* bad?:

@Bulb said in Bad code? As in *really* bad?:

C has exactly the right building blocks. It should have a library on top of them though.

A decent string variable type should grow and get freed automatically when out of scope, that requires at least something like destructors.

It also requires a garbage collector

masonwheeler

@RaceProUK No it doesn't. It can be done just fine with reference counting.

heterodox

@masonwheeler And the reference count is then used by...?

masonwheeler

@heterodox By the compiler. That's how strings are implemented in Delphi: the compiler inserts calls to functions that increase or decrease the reference count in appropriate places, and when the decrease function sees the count fall to 0, it deallocates the string.

It's possible to deliberately write malicious code to break this system, but you have to know what you're doing on a very low level and really go out of your way to do it. Aside from that, the string tracking is rock-solid, no GC required.

RaceProUK

@masonwheeler said in Bad code? As in *really* bad?:

That's how strings are implemented in Delphi: the compiler inserts calls to functions that increase or decrease the reference count in appropriate places, and when the decrease function sees the count fall to 0, it deallocates the string.

So, Delphi uses a deterministic garbage collector.

masonwheeler

@RaceProUK No, it uses a reference counting system. Most developers agree that that's something completely different from GC, which involves a tracing mechanism of some sort.

<>WORDS HAVE MEANINGS!!!</>

RaceProUK

@masonwheeler said in Bad code? As in *really* bad?:

Most developers agree that that's something completely different from GC, which involves a tracing mechanism of some sort.

Reference counting, usually.

masonwheeler

@RaceProUK ...

But just to give you the benefit of the doubt:

difference between garbage collection and reference counting - Google Search

RaceProUK

@masonwheeler If garbage collection is so different to reference counting, why does the MSDN documentation about .NET garbage collection keep talking about references? It's almost like it has to know how many references an object has so it knows if it can collect the gargabe… Almost like it's counting them…

masonwheeler

@RaceProUK No, not like it's counting them at all. There's no concept of "count" in a garbage collector; the only count it cares about is "zero or nonzero". If any live reference exists--no matter how many--the object isn't garbage and can't be collected, and that's all it cares about.

A reference-counting system is completely different on a conceptual level. There isn't an external garbage collection subsystem tracking whether references are live or not; the count is stored as a part of the data being counted, and there's code that actively increases and decreases it when references are added or removed.

RaceProUK

@masonwheeler said in Bad code? As in *really* bad?:

the only count it cares about is "zero or nonzero"

Thank you for proving my point for me.

masonwheeler

@RaceProUK

Are you seriously not understanding the essential difference here?

dkf

@Bulb said in Bad code? As in *really* bad?:

how each compiler chose to lay out the variables

Each compiler was gcc. Probably about the same version; gcc wasn't evolving very rapidly in the late 1990s…

dkf

@RaceProUK said in Bad code? As in *really* bad?:

If garbage collection is so different to reference counting

They're a bit different. In reference counting, you keep a counter in each referencable object and deallocate the object (possibly also calling some sort of callback) when the number of references drops to zero. There has to be quite a bit of book-keeping inserted in various places to keep the reference counters accurate, but the cost of deallocation is usually spread evenly across the application.

In garbage collection, the compiler instead keeps track of where the roots of graphs of objects are. In the simplest form of GC, the garbage collector periodically goes through the set of currently active roots and marks all the objects that are reachable from it. It then sweeps the space of all objects and deallocates any unmarked objects. This has the advantage of being able to safely deallocate much more complex memory objects (e.g., circular structures, complex entities like closures) but has a downside of needing the program to pause while it is working. There's been a lot of work put into improving on this (such as generational GC and concurrent GC) but there's usually a full stop-the-world-for-mark-and-sweep GC as a fallback as that does the best job at releasing unused memory.

The biggest practical problem with GC is that you can really only have one GC system in charge at a time (they work very poorly when hybridised with non-GC systems), and the second big problem is that they've a bit of a tendency to be inclined to being more memory hungry (which can reduce memory locality too, which induces subtle memory-related performance troubles). The big benefit is that, provided everything you're doing is using the GC (e.g., because it's using the CLR or the JVM) then memory handling is almost always trivial for the rest of the program's code; it's just allocate when need, use as required, and then forget about doing anything else. (Unless you're doing clever caching or something like that, when you ought to use a framework-supplied class to handle the trickiness.)

FWIW, fixing refcount handling bugs is hard. BTDT…

Arantor

@masonwheeler There are multiple ways that a garbage collector can work, but reference counting seems to be amongst the most common implemented across languages that are garbage collected. They are separate concepts but with some hefty overlap.

dkf

@Arantor said in Bad code? As in *really* bad?:

reference counting seems to be amongst the most common implemented across languages that are garbage collected

It's the simplest to explain to another programmer, and it has the advantage of being easy to do a basic implementation of. It's just that it is the devil to debug when you get it wrong. (Yes, I've written refcounting systems.) The major downside is that it requires that your entire space of objects must be describable as a DAG; loops (well, loops with ownership) are utterly forbidden. This in turn means that you need to go down the route of things like copy-on-write value semantics, etc. The consequences are definitely far-reaching.

Full GC is more general. It's probably really hard to get right, but I've never actually written an implementation; most of the documentation on how to go about it tends to be more than a bit impenetrable and gnostic. I mentioned some downsides above, but another one is that the time that a particular value is deallocated is highly uncertain; it depends on when the GC actually does a collection, and that can be painful when the object is tied to an expensive external resource. The typical riposte to that is to go to an explicit close action instead of relying on a finalizer or destructor, often with syntax (see C#'s using or Java's try-with-resources or Python's with, though none of them are original) to support guaranteed calling coupled to leaving a program context.

wharrgarbl

@RaceProUK the "reference counting" name is usually used for a much simpler thing, were a counter is stored with the object, and there is increment and decrement code everywhere it's passed along, and it's freed after a decrement to 0. In C this code is usually done manually, and in other languages it's generated by the compiler.

It has a flaw where two objects can reference each other and never get free.

Anything we call garbage collector uses better algorithms that doesn't lose memory to circular references like that.

Arantor

@wharrgarbl I like how PHP's garbage collector suddenly isn't a garbage collector just because it can be tripped up by circular references.

Bulb

@wharrgarbl said in Bad code? As in *really* bad?:

A decent string variable type should grow and get freed automatically when out of scope, that requires at least something like destructors.

Well, C does not have those, so it can't. But in C that's OK. In C, nothing is freed automatically, so why should strings?

This is intentional. In C, nothing happens without being explicitly stated in the code, which provides better control, which is needed in some cases. In all other cases, which is vast majority of them, a higher level language is more appropriate.

@RaceProUK said in Bad code? As in *really* bad?:

It also requires a garbage collector

Ownership is good enough.

Note that in C++, std::string is not reference-counted. It simply owns the memory and compiler injects direct all to deallocate when it goes out of scope. So does Rust std::string::String.

@masonwheeler said in Bad code? As in *really* bad?:

That's how strings are implemented in Delphi: the compiler inserts calls to functions that increase or decrease the reference count in appropriate places

Reference-counted strings were initially tried in C++ and it turned out it does not pay off and it complicated the semantics. So they are not.

@RaceProUK said in Bad code? As in *really* bad?:

@masonwheeler said in Bad code? As in *really* bad?:

Most developers agree that that's something completely different from GC, which involves a tracing mechanism of some sort.

Reference counting, usually.

A general reference-counting that applies to all objects and infers what to count from the language itself might be considered a case of garbage collector in the general sense.

But we are not talking about that. We are talking about object that behaves as value from the language point of view and is internally copy-on-write and managed by reference counting. That's much less than garbage collector.

Bulb

@dkf said in Bad code? As in *really* bad?:

Each compiler was gcc. Probably about the same version; gcc wasn't evolving very rapidly in the late 1990s…

Gcc did have very good optimizations in place by then, so the same version targeting different platforms could easily lay things out differently because the instructions it chose to use had different constraints.

dkf

@Arantor said in Bad code? As in *really* bad?:

I like how PHP's garbage collector suddenly isn't a garbage collector just because it can be tripped up by circular references.

It's a matter of terminological strictness. If reference counting is garbage collection (as opposed to being just a related technology) then it is a very weak one, precisely because complex object graphs will get leaked rather than reclaimed. The up-side of reference counting is that (when it is working correctly) it frees memory about as early as it is possible to do, which helps keep the size of the working set down. That's pretty good, as it helps promote better performance; eventually that'll enable the overall performance of PHP to be really quite good (getting the types right will do most of the rest; my experience suggests that that'll enable a really good implementation strategy).

Arantor

@dkf I'd need to go play in the internals to know for sure, but refcounting was the principle route in 5.x, but it wasn't run as early as possible - since PHP is intended as short lived scripts, it was frequently the case that things would fall out of scope, no refs remaining, but not call the GC until end of script.

I don't know what's changed under the hood in 7 to make everything a lot faster without apparently breaking much backwards compatibility.

dkf

@Bulb said in Bad code? As in *really* bad?:

Reference-counted strings were initially tried in C++ and it turned out it does not pay off and it complicated the semantics. So they are not.

IIRC, isn't reference counting available as its own thing? Hmm, yes. std::shared_ptr. Good that it's not bolted into std::string.

Bulb

@dkf said in Bad code? As in *really* bad?:

The up-side of reference counting is that (when it is working correctly) it frees memory about as early as it is possible to do, which helps keep the size of the working set down. That's pretty good, as it helps promote better performance; eventually that'll enable the overall performance of PHP to be really quite good (getting the types right will do most of the rest; my experience suggests that that'll enable a really good implementation strategy).

Yet, generational collectors with copying from first generation generally beat reference-counting implementations hands down. Because the atomic increments and decrements all over the place incur quite large overhead and do nothing to simplify allocation, while copying generational collectors make allocation a matter of increment and deallocation a matter of nothing at all.

Case in the point: Vala code is often slower than C# one, even with Mono, which used the relatively poor conservative Boehm–Demers–Weiser garbage collector.

The only thing that beats good collector is ownership tracking with good utilization of the stack, which is error-prone in C++ and difficult to learn in Rust.

@dkf said in Bad code? As in *really* bad?:

IIRC, isn't reference counting available as its own thing? Hmm, yes. std::shared_ptr. Good that it's not bolted into std::string.

Yes, it is available. It's recommended to use it sparingly, because it is not exactly fast.

But the main reason it is not bolted into std::string is that it is allowed to edit string in place and the way operator[] is designed in C++ does not allow intelligent copy-on-write. And since everybody learned to pass std::string by const reference anyway, copying strings is not that common.

cvi

@Bulb said in Bad code? As in *really* bad?:

Reference-counted strings were initially tried in C++ and it turned out it does not pay off and it complicated the semantics.

IIRC libstdc++ (GCC's standard library) did ship with a std::string that was reference counted for a while. From what I understand, the new standards (C++11+) prohibit this, though (or, at least, make it impossible to create a reference counted implementation that conforms to the standard). Modern std::string implementations may use a small-string optimization, where strings up to a certain length are embedded into the std::string instance, and thus don't require allocations.

edit: what Bulb said.

Bulb

@cvi said in Bad code? As in *really* bad?:

IIRC libstdc++ (GCC's standard library) did ship with a std::string that was reference counted for a while.

I am not sure about libstdc++, but I remember Microsoft one did. Most of them did, in fact.

@cvi said in Bad code? As in *really* bad?:

From what I understand, the new standards (C++11+) prohibit this

Actually, I am pretty sure all standards require that:

the string may be edited in place via char &operator[](size_t) and via non-const iterators,
and the changes shall not propagate to other instances.

Those methods get called even for read, with no way to intercept the actual write. So it is not really prohibited, but there is no way to make it both conformant and actually useful.

The versions of standard libraries that did have reference-counted std::string all predate C++98.

dkf

@Bulb said in Bad code? As in *really* bad?:

Yet, generational collectors with copying from first generation generally beat reference-counting implementations hands down. Because the atomic increments and decrements all over the place incur quite large overhead and do nothing to simplify allocation, while copying generational collectors make allocation a matter of increment and deallocation a matter of nothing at all.

You can get a lot better code if you can guarantee to restrict objects to a single thread (does anyone have a way to properly express that application-level guarantee to a compiler? I've got code where it would be perfect for enabling higher degrees of optimisation, and the memory allocator in use is already using thread-specific arenas). That lets you get rid of all of that atomic stuff, and the compiler can sensibly optimise the refcounting to about the cost of doing ownership tracking. It's the thread handling that makes it all a PITA, but that's threads all over.

cvi

@Bulb said in Bad code? As in *really* bad?:

Actually, I am pretty sure all standards require that:

the string may be edited in place via char &operator and via non-const iterators,

and the changes shall not propagate to other instances.

Those methods get called even for read, with no way to intercept the actual write. So it is not really prohibited, but there is no way to make it both conformant and actually useful.

Seems like std::string is actually refcounted until GCC 5.x, where they switch to the SSO version. In 4.x the non-const version of operator[] "unshares" (their words) the string.

The new thing with C++11 is that operator[] isn't allowed to invalidate existing pointers (from data() or whatever), which makes the above non-conforming (AFAIK).

Whether or not the refcounted implementation is useful is debatable. As you mention, most people would pass the string by const-ref, so it doesn't really matter there. I guess if you were to create a string, and then insert it into some data structure for longer storage, you'd save an allocation with refcounting prior to C++11 where move-semantics weren't a thing yet?

cvi

@dkf said in Bad code? As in *really* bad?:

You can get a lot better code if you can guarantee to restrict objects to a single thread (does anyone have a way to properly express that application-level guarantee to a compiler? I've got code where it would be perfect for enabling higher degrees of optimisation, and the memory allocator in use is already using thread-specific arenas).

The C++ solution would be to stuff this as a trait/aspect/policy into some template argument. You'll end up with distinct types for cross-thread and single-thread objects, though, so the distinction must be known at compile time.

If you're OK with implementation-specific code, you can probably make the types compatible in the sense that converting from one to the other ends up being free on e.g. x86. (The ref-counter is simply incremented with different instructions in the two cases, but their memory layout remains the same.)

Bulb

@dkf said in Bad code? As in *really* bad?:

does anyone have a way to properly express that application-level guarantee to a compiler?

Yes, Rust. You have normal objects that have single owner, verified at compile time, and then non-thread-safe and thread-safe variants of smart pointers. And the compiler can guarantee that the non-thread-safe ones are not shared between threads.

@cvi said in Bad code? As in *really* bad?:

The C++ solution would be to stuff this as a trait/aspect/policy into some template argument. You'll end up with distinct types for cross-thread and single-thread objects, though, so the distinction must be known at compile time.

But C++ can't check that you don't share the non-safe variant. Rust can.

cvi

@Bulb said in Bad code? As in *really* bad?:

But C++ can't check that you don't share the non-safe variant.

True. Guess it depends what you're after. You can use non-atomic reference counted objects across multiple threads if you protect regions with potential updates otherwise (e.g., a single mutex for an update that touches large numbers of the objects).

Edit: In this case, I wouldn't make the aspect to mean "restricted to a single thread" or "shared across threads", but more explicitly "atomically reference counted" or "non-atomically reference counted". If you have built-in support for the former (which Rust seems to have), the compiler may be able to produce better code in other situations too. So, I guess, it's more general in that sense.

dkf

@Bulb said in Bad code? As in *really* bad?:

Yes, Rust.

That's formally a non-answer (and would require major code rewriting, which is about as popular as a bucket of cold cat vomit). I was actually interested most particularly in how to do it in LLVM IR; I happen to know that I'm working at a lower level than Rust because I know a reasonable amount of bug reports against LLVM submitted by the Rust implementers. :)

masonwheeler

@Bulb said in Bad code? As in *really* bad?:

the atomic increments and decrements all over the place incur quite large overhead

This hasn't been true for many processor generations now, on mainstream commercial CPUs at least. Unless another core currently has the memory address in its cache, which is pretty rare, atomic increments and decrements are barely more expensive than the non-atomic versions.

wharrgarbl

@Arantor said in Bad code? As in *really* bad?:

@wharrgarbl I like how PHP's garbage collector suddenly isn't a garbage collector just because it can be tripped up by circular references.

I never heard/read the expression "garbage collector" before Java. You're freeing the memory instantly, it's a different thing. In java you're piling up garbage in your curb, and wait for the garbage truck collects it.

Arantor

@wharrgarbl this is how OHP's GC works. Just typically the call is made at end of script.

cvi

@masonwheeler said in Bad code? As in *really* bad?:

@Bulb said in Bad code? As in *really* bad?:

the atomic increments and decrements all over the place incur quite large overhead

This hasn't been true for many processor generations now, on mainstream commercial CPUs at least. Unless another core currently has the memory address in its cache, which is pretty rare, atomic increments and decrements are barely more expensive than the non-atomic versions.

Not so sure about that. LOCK ADD for instance has a minimum of 17 cycles latency on Ryzen (vs 6 for a normal ADD, and XADD is worse). On skylake, you can do an LOCK ADD every 18 cycles (vs an ADD twice per clock cycle). Plus, the locked versions always have one memory operand. Source

There are some claims that a locked instruction costs you as much as a cache miss typically. Seems to be little information on this, and the post in question is a bit older by now.

On a personal note, I've seen lock add turn up as a bottleneck in some code. (FWIW- the code wasn't very good, it passed and returned a lot of shared_ptrs in its innermost loop. It's not an entirely fair comparison since not doing that also eliminated that particular code entirely).

masonwheeler

@cvi I'm not talking about LOCK ADD, I'm talking about LOCK INC.

cvi

@masonwheeler "INC" has the same characteristics as "ADD" from what I can see. Probably same µcode under the hood. Besides, GCC/Clang generate "LOCK ADD" for std::atomic. CL uses "LOCK XADD" for some reason.

Medinoc

As far as I know, MFC's CString class (and more modern -- yet still a decade old -- CStringT template) uses refcounted copy-on-write too. They don't have to make it follow the C++ standard like std::string, and I bet changing it would cause more code-breaking problems than it could ever solve.