Path: csiph.com!eternal-september.org!reader02.eternal-september.org!.POSTED!not-for-mail From: Tim Rentsch Newsgroups: comp.lang.c Subject: Re: A defer mechanism for C Date: Sun, 27 Dec 2020 04:57:37 -0800 Organization: A noiseless patient Spider Lines: 104 Message-ID: <86tus7wgn2.fsf@linuxsc.com> References: <3a965b75-7eb6-4287-8e19-8969b6628d90n@googlegroups.com> <0b136e48-e0e7-45f4-a6de-8a5406cefff2n@googlegroups.com> <81f236a7-76cc-499d-91c1-aff76ea471c2n@googlegroups.com> <87v9cwb4di.fsf@nosuchdomain.example.com> <87zh26ajdu.fsf@nosuchdomain.example.com> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Injection-Info: reader02.eternal-september.org; posting-host="7428659b5bf23ec7739a8c9d5f9c9404"; logging-data="12195"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1/KS/39wA1Qqt6FAx8zrPBmv2ZVHNJQW4g=" User-Agent: Gnus/5.11 (Gnus v5.11) Emacs/22.4 (gnu/linux) Cancel-Lock: sha1:XjOFbY9e4TrRF6PMyEjxs4hDAWE= sha1:ihyEMj1NL28ifnPXIQjIUOG6nnk= Xref: csiph.com comp.lang.c:157813 Keith Thompson writes: > David Brown writes: > >> On 20/12/2020 21:37, Keith Thompson wrote: >> >>> David Brown writes: >>> >>>> On 20/12/2020 17:46, Christian Hanne wrote: >>>> >>>>>>> I can guarantee, without any doubt whatsoever, that the fastest malloc >>>>>>> implementation you will ever see is the algorithm used by FreeRTOS's >>>>>>> "heap_1" allocator. It will easily beat MS's algorithm, regardless of >>>>>>> the size of the blocks or the number of them, and it will not waste any >>>>>>> space beyond what you might need for alignment. It will beat any >>>>>>> size-specific pool-based system. However, it has one weakness - "free" >>>>>>> is a no-op. >>>>> >>>>> Forget it, a malloc()-implementation without free isn't a >>>>> malloc()-implementation. >>>> >>>> If it gives memory when you call malloc, it is entirely fine. There are >>>> no specifications that require heap memory to be re-usable. >>> >>> Well, there's the C standard, which says: >>> >>> The free function causes the space pointed to by ptr to be >>> deallocated, that is, made available for further allocation. >>> >>>> There are a great many programs that allocate memory dynamically at >>>> startup or early on, and never need to free anything until the end of >>>> the program (or for many embedded systems, simply never end and never >>>> need to free anything). For hosted systems, the OS will clear up the >>>> memory when the program ends. Any effort made by the program or >>>> libraries to track the allocated memory, re-use memory, or free it is >>>> then wasted effort. >>> >>> An implementation in which free() is a no-op might be useful, but it's >>> not conforming. >> >> Is it possible to write a program that uses only standards-defined >> behaviour and could tell the difference between a malloc/free >> implementation that recycles freed memory, and one where free is a >> no-op? I don't think so - but I might be missing something. And if >> there is no way to tell the difference, how could it not be conforming? >> >> The /intention/ of how free should behave is clear in the standards, and >> a no-op free doesn't follow that. >> >> (The usefulness of a no-op free implementation is primarily in cases >> where you either don't call "free" until the end of the program, or the >> program never ends and you don't call "free" at all. In such code, >> since you don't ask for more memory afterwards, there is no difference >> in how free behaves.) > > Well, there's some wiggle room. If the standard states that something > is a requirement, I tend to think that it's a requirement, even if > it's difficult to write a program that can tell the difference. The question is What /is/ the requirement? Calling free() with a pointer to some previously malloc()'ed memory doesn't require that a subsequent malloc() call be able to re-use that memory. Under the as-if rule, free() doing nothing satisfies the stated specifications. > On the other hand, N1570 5.1.2.3p6 defines the "least requirements > on a conforming implementation" in terms of observable behavior. Exactly. > On the other other hand, as James Kuyper points out, a program that > repeated mallocs and frees a chunk of memory will eventually crash if > free is a no-op, but should run indefinitely if it works as required. > A number of allocations equal to 2**N, where N is the number of > bits in a void*, should suffice (as long as the allocations can't > be optimized away). But at one allocation per nanosecond, that could > take nearly 6 centuries on a 64-bit system. His argument is unsound. Consider the following implementation of malloc() and free(): malloc(): make an OS call to get some memory if we got some, return a pointer to that otherwise, return NULL free(): if the argument is NULL, nothing otherwise, make an OS call to return the allocated space to the OS pool This implementation satisfies both the letter and the spirit of what the C standard says about malloc() and free(). Yet a call to malloc() may fail at any time, for reasons having nothing to do with what our C program is doing. Any sequence of calls to malloc() and free(), with any results from the malloc() calls, cannot be distinguished from an identical sequence of calls that is possible on this implementation. Since malloc() and free() as shown above are conforming, no conclusion can be drawn from any sequence of results from malloc()/free() calls as to whether the implementation is conforming. As far as observable behavior goes, free() can do anything at all, including nothing, as long as malloc() returns either NULL or a valid pointer to allocated space.