I have to concede Branden's "gotcha". Struct copying is definitely not O(1).

A real-life hazard of non-O(1) operations. Vic Vyssotsky put bzero (I forget what Vic called it) into Fortran II. Sometime later, he found that a percolation simulation was running annoyingly slowly. It took some study to discover that the real inner loop of the program was not the percolation, which touched only a small fraction of a 2D field. More time went into the innocuous bzero initializer. The fix was to ADD code to the inner loop to remember what entries had been touched, and initialize only those for the next round of the simulation.

> for a while, every instruction has [sic] an exactly predictable and constant cycle

>  count. ...[Then] all of a sudden you had instructions with O(n) cycle counts.

O(n) cycle counts were nothing  new. In the 1950s we had the IBM 1620 with arbitrary-length arithmetic and the 709 with "convert" instructions whose cycle count went up to 256.

>> spinelessly buckled to allow malloc(0) to return 0, as some
>> implementations gratuitously did.

> What was the alternative?  There was no such thing as an exception, and
> if a pointer was an int and an int was as wide as a machine address,
> there'd be no way to indicate failure in-band, either.

What makes you think allocating zero space should fail? If the size n of a set is determined at run time, why should one have to special-case its space allocation when n=0?  Subsequent processing of the form for(i=0; i<n; i++) {...} will handle it gracefully with no special code. Malloc should do as it did in v7--return a non-null pointer different from any other active malloc pointer, as Bakul stated. If worse comes to worst[1] this can be done by padding up to the next feasible size. Regardless of how the pointer is created, any access via it would of course be out of bounds and hence wrong. 

> How does malloc(0) get this job done and what benefit does it bring?

If I understand the "job" (about initializing structure members) correctly, malloc(0) has no bearing on it. The benefit lies elsewhere.

Apropos of tail calls, Rob Pike had a nice name for an explicit tail call, "become". It's certainly reasonable, though, to make compilers recognize tail calls implicitly.

[1] Worse didn't come to worst in the original malloc. It attached metadata to each block, so even blocks of size zero consumed some memory.

Doug

On Sat, Sep 28, 2024 at 1:59 PM Bakul Shah via TUHS <tuhs@tuhs.org> wrote:

Just responding to random things that I noticed:

You don't need special syntax for tail-call. It should be done transparently when a call is the last thing that gets executed. Special syntax will merely allow confused people to use it in the wrong place and get confused more.

malloc(0) should return a unique ptr. So that "T* a = malloc(0); T* b = malloc(0); a != (T*)0 && a != b". Without this, malloc(0) acts differently from malloc(n) for n > 0.

Note that except for arrays, function arguments & result are copied so copying a struct makes perfect sense. Passing arrays by reference may have been due to residual Fortran influence! [Just guessing] Also note: that one exception has been the cause of many problems.

In any case you have not argued convincingly about why dynamic memory allocation should be in the language (runtime) :-) And adding that wouldn't have fixed any of the existing problems with the language.

Bakul

> On Sep 28, 2024, at 9:58 AM, G. Branden Robinson <g.branden.robinson@gmail.com> wrote:
>
> At 2024-09-28T09:34:14-0400, Douglas McIlroy wrote:
>>> C's refusal to specify dynamic memory allocation in the language
>>> runtime (as opposed to, eventually, the standard library)
>>
>> This complaint overlooks one tenet of C: every operation in what you
>> call "language runtime" takes O(1) time. Dynamic memory allocation
>> is not such an operation.
>
> A fair point.  Let me argue about it anyway.  ;-)
>
> I'd make three observations.  First, K&R did _not_ tout this in their
> book presenting ANSI C.  I went back and checked the prefaces,
> introduction, and the section presenting a simple malloc()/free()
> implementation.  The tenet you claim for the language is not explicitly
> articulated and, if I squint really hard, I can only barely perceive
> (imagine?) it deeply between the lines in some of the prefatory material
> to which K&R mostly confine their efforts to promote the language.  In
> my view, a "tenet" is something more overt: the sort of thing U.S.
> politicians try to get hung on the walls of every public school
> classroom, like Henry Spencer's Ten Commandments of C[1] (which itself
> does not mention this "core language has only O(1) features" principle).
>
> Second, in reviewing K&R I was reminded that structure copying is part
> of the language.  ("There are no operations that manipulate an entire
> array or string, although structures may be copied as a unit."[2])
> Doesn't that break the tenet right there?
>
> Third, and following on from the foregoing, your point reminded me of my
> youth programming non-pipelined machines with no caches.  You could set
> your watch by (just about) any instruction in the set--and often did,
> because we penurious microcomputer guys often lacked hardware real-time
> clocks, too.  That is to say, for a while, every instruction has an
> exactly predictable and constant cycle count.  (The _value_ of that
> constant might depend on the addressing mode, because that would have
> consequences on memory fetches, but the principle stood.)  When the Z80
> extended the 8080's instruction set, they ate from Tree of Knowledge
> with block-copy instructions like LDIR and LDDR, and all of a sudden you
> had instructions with O(n) cycle counts.  But as a rule, programmers
> seemed to welcome this instead of recognizing it as knowing sin, because
> you generally knew worst-case how many bytes you'd be copying and take
> that into account.  (The worst worst case was a mere 64kB!)
>
> Further, Z80 home computers in low-end configurations (that is, no disk
> drives) often did a shocking thing: they ran with all interrupts masked.
> All the time.  The one non-maskable interrupt was RESET, after which you
> weren't going to be resuming execution of your program anyway.  Not from
> the same instruction, at least.  As I recall the TRS-80 Model I/III/4
> didn't even have logic on the motherboard to decode the Z80's "interrupt
> mode 2", which was vectored, I think.  Even in the "high-end"
> configurations of these tiny machines, you got a whopping ONE interrupt
> to play with ("IM 1").
>
> Later, when the Hitachi 6309 smuggled similar block-transfer decadence
> into its extensions to the Motorola 6809 (to the excitement of we
> semi-consciously Unix-adjacent OS-9 users) they faced a starker problem,
> because the 6809 didn't wall off interrupts in the same way the 8080 and
> Z80.  They therefore presented the programmer with the novelty of the
> restartable instruction, and a new generation of programmers became
> acquainted with the hard lessons time-sharing minicomputer people were
> familiar with.
>
> My point in this digression is that, in my opinion, it's tough to hold
> fast to the O(1) tenet you claim for C's core language and to another at
> the same time: the language's identity as a "portable assembly
> language".  Unless every programmer has control over the compiler--and
> they don't--you can't predict when the compiler will emit an O(n) block
> transfer instruction.  You'll just have to look at the disassembly.
>
> _Maybe_ you can retain purity by...never copying structs.  I don't think
> lint or any other tool ever checked for this.  Your advocacy of this
> tenet is the first time I've heard it presented.
>
> If you were to suggest to me that most of the time I've spent in my life
> arguing with C advocates was with rotten exemplars of the species and
> therefore was time wasted, I would concede the point.
>
> There's just so danged _many_ of them...
>
>> Your hobbyhorse awakened one of mine.
>>
>> malloc was in v7, before the C standard was written. The standard
>> spinelessly buckled to allow malloc(0) to return 0, as some
>> implementations gratuitously did.
>
> What was the alternative?  There was no such thing as an exception, and
> if a pointer was an int and an int was as wide as a machine address,
> there'd be no way to indicate failure in-band, either.
>
> If the choice was that or another instance of atoi()'s wincingly awful
> "does this 0 represent an error or successful conversion of a zero
> input?" land mine, ANSI might have made the right choice.
>
>> I can't imagine that any program ever actually wanted the feature. Now
>> it's one more undefined behavior that lurks in thousands of programs.
>
> Hoare admitted to only one billion-dollar mistake.  No one dares count
> how many to write in C's ledger.  This was predicted, wasn't it?
> Everyone loved C because it was fast: it was performant, because it
> never met a runtime check it didn't eschew--recall again Kernighan
> punking Pascal on this exact point--and it was quick for the programmer
> to write because it never met a _compile_-time check it didn't eschew.
> C was born as a language for wizards who never made mistakes.
>
> The problem is that, like James Madison's fictive government of angels,
> such entities don't exist.  The staff of the CSRC itself may have been
> overwhelmingly populated with frank, modest, and self-deprecating
> people--and I'll emphasize here that I'm aware of no accounts that this
> is anything but true--but C unfortunately played a part in stoking a
> culture of pretension among software developers.  "C is a language in
> which wizards program.  I program in C.  Therefore I'm a wizard." is how
> the syllogism (spot the fallacy) went.  I don't know who does more
> damage--the people who believe their own BS, or the ones who know
> they're scamming their colleagues.
>
>> There are two arguments for malloc(0), Most importantly, it caters for
>> a limiting case for aggregates generated at runtime--an instance of
>> Kernighan's Law, "Do nothing gracefully". It also provides a way to
>> create a distinctive pointer to impart some meta-information, e.g.
>> "TBD" or "end of subgroup", distinct from the null pointer, which
>> merely denotes absence.
>
> I think I might be confused now.  I've frequently seen arrays of structs
> initialized from lists of literals ending in a series of "NULL"
> structure members, in code that antedates or ignores C99's wonderful
> feature of designated initializers for aggregate types.[3]  How does
> malloc(0) get this job done and what benefit does it bring?
>
> Last time I posted to TUHS I mentioned a proposal for explicit tail-call
> elimination in C.  I got the syntax wrong.  The proposal was "return
> goto;".  The WG14 document number is N2920 and it's by Alex Gilding.
> Good stuff.[4]  I hope we see it in C2y.
>
> Predictably, I must confess that I didn't make much headway on
> Schiller's 1975 "secure kernel" paper.  Maybe next time.
>
> Regards,
> Branden
>
> [1] https://web.cs.dal.ca/~jamie/UWO/C/the10fromHenryS.html
>
>    I can easily imagine that the tenet held at _some_ point in the
>    C's history.  It's _got_ to be the reason that the language
>    relegates memset() and memcpy() to the standard library (or to the
>    programmer's own devise)!  :-O
>
> [2] Kernighan & Ritchie, _The C Programming Language_, 2nd edition, p. 2
>
>    Having thus admitted the camel's nose to the tent, K&R would have
>    done the world a major service by making memset(), or at least
>    bzero(), a language feature, the latter perhaps by having "= 0"
>    validly apply to an lvalue of non-primitive type.  Okay,
>    _potentially_ a major service.  You'd still need the self-regarding
>    wizard programmers to bother coding it, which they wouldn't in many
>    cases "because speed".  Move fast, break stuff.
>
>    C++ screwed this up too, and stubbornly stuck by it for a long time.
>
>    https://cplusplus.github.io/CWG/issues/178.html
>
> [3] https://gcc.gnu.org/onlinedocs/gcc/Designated-Inits.html
> [4] https://www.open-std.org/jtc1/sc22/wg14/www/docs/n2920.pdf