Bug analysis

[Spiros Bousbouras]

I've come to the opinion that
realloc creates buggy code. Simple and plain. I've never used it once.

I don't see how you can get by without realloc() at least
on the desktop. Plus I don't think it's that dangerous. One
only needs to take care not to have multiple pointers pointing
inside the malloced/realloced area but only one pointing
to the beginning and otherwise use offsets.

 

[John Doe]

The Standard does not forbid writing '\0' to a text stream
(or trying to), but doesn't guarantee it can be read back again.
7.19.2p2: "[...] Data read in from a text stream will necessarily
compare equal to the data that were earlier written out to that
stream only if: the data consist only of printing characters and
the control characters horizontal tab and new-line; no new-line
character is immediately preceded by space characters; and the last
character is a new-line character. [...]" That is, if you've got
a text file that contains '\0' (or '\r', '\a', '\033', ...) you're
already on shaky ground.

And what if we haven't ever written to that stream? If the file's come
from who knows where, is there anything we are guaranteed?
The whole contents of 7.19.2p2 is still more depressing.

 

[John Doe]

The whole contents of 7.19.2p2 is still more depressing.

Sorry, what actually "depressed" me was 7.19.2p3:

Data read in from a binary stream shall compare equal to the data that
were earlier written out to that stream, under the same implementation.
Such a stream may, however, have an implementation-defined number of
null characters appended to the end of the stream.

Even if the committee had felt it desirable to legislate C's
I/O interactions with all conceivable sources and sinks of data,
I don't see how it could have been practical. Data exchange with
"who knows where" is just too big and too complex a topic.

I thought it was so easy. Under your implementation you write (even in
binary mode) 'H' 'e' 'l' 'l' 'o' '\0' bytes to a file and send it to me.
I receive the file, open it under my implementation (which doesn't
distinguish between binary and text mode) and read "Hello" plus those
nulls at the end. But... can you guarantee me what will I read?

 

[CBFalconer]

John Doe wrote:
.... snip ...


What guarantees could a C Standard make about reading files
written by Fortran programs, say? If a COBOL producer uses PRINT
AFTER ADVANCING 3 LINES, what characters should a C consumer read?

How about 'printf("\n\n\n%s", "the string");'

 

[CBFalconer]

.... snip ...

When Chuck came out with a version of ggets that had realloc
trouble, I quipped, "For memory management in C, does everyone
need to have Heathfield on speed-dial?"

I object. ggets has no realloc trouble.

 

[CBFalconer]

CBFalconer said:

No, but its users might. Your ggets routine has a linear
reallocation strategy, which can have quite a serious
performance impact compared to a quadratic strategy.

You mistake efficiency in applications that will not occur for
actual efficiency. The intended, and expected, use of ggets is in
interactive input. The strings will not become unceasingly large,
so the linear reallocation is used, and is most efficient for
interactive input. Note that the system will work correctly, if
not quite as efficiently, for any length of input string. Thus the
user is not limited in application, but the normal use is
efficient. The initial allocation often suffices.

Incidentally a reasonably smart malloc package will make those
reallocs quite efficient. They simply detect that the original
assignment can be expanded in place, and avoid doing any copying.
When such an expansion is impossible they go through the full
alloc/dealloc gyration. See my nmalloc package.

 

[Keith Thompson]

You mistake efficiency in applications that will not occur for
actual efficiency. The intended, and expected, use of ggets is in
interactive input. The strings will not become unceasingly large,
so the linear reallocation is used, and is most efficient for
interactive input. Note that the system will work correctly, if
not quite as efficiently, for any length of input string. Thus the
user is not limited in application, but the normal use is
efficient. The initial allocation often suffices.

[...]

For interactive input, huge lines are probably errors; it would be
simpler to use a fixed-size buffer and discard anything beyond the
maximum (returning an error indication to the caller, of course).

Actually handling arbitrarily long input lines makes more sense for
reading from files.

 

[Richard Tobin]

Incidentally a reasonably smart malloc package will make those
reallocs quite efficient.

Are there any modern realloc()s in common use where this isn't true?
It makes much more sense for it to be done at that level: a user-written
increasing-realloc may interact badly with the system one (e.g. suppose
you use powers of two, but the system one has a per-block overhead).

-- Richard

 

[Richard]

CBFalconer said:


Yes, I guessed you'd say that. But where is your interactive input
coming from? stdin, right? And when people write programs that read
from stdin, it's only a matter of time before they start storing
the input in a file and directing the input from the file to the
program, right? And before you know it, they're using some other
program to create the input, right? And suddenly the input isn't
interactive after all. What would you have them do then? Stop using
ggets? If so, then better not to use it in the first place - lower
maintenance cost.

And there we have it : with a stroke and a glance a long way into the
future Chuck's ggets is consigned to the rubbish it. After all, we would
be better off not using it in the first place!

 

[CBFalconer]

CBFalconer said:

Yes, I guessed you'd say that. But where is your interactive input
coming from? stdin, right? And when people write programs that read
from stdin, it's only a matter of time before they start storing
the input in a file and directing the input from the file to the
program, right? And before you know it, they're using some other
program to create the input, right? And suddenly the input isn't
interactive after all. What would you have them do then? Stop using
ggets? If so, then better not to use it in the first place - lower
maintenance cost.

No, since the action of storing the input in a file and then
feeding that does NOT affect the length of the strings. Go back to
the part you snipped and read it.

 

[CBFalconer]

Are there any modern realloc()s in common use where this isn't
true? It makes much more sense for it to be done at that level:
a user-written increasing-realloc may interact badly with the
system one (e.g. suppose you use powers of two, but the system
one has a per-block overhead).

I think you oversnipped and are confusing the selection of the
sizes with the actual realloc action.

 

[CBFalconer]

.... snip ...

I read it the first time. If you think your nmalloc package
overcomes the inherent inefficiency of linear reallocation
strategies, feel free to explain how.

It avoids SOME of the inefficiency, by avoiding moving the original
allocation wheneve possible.

 

[CBFalconer]

CBFalconer said:

And how does it do that - by allocating larger blocks to begin
with?

The source is available on my page. However, it fundamentally
looks for vacant space adjacent to the top of the original block.
It can decide this quickly. Then it checks whether that space is
sufficient for the expansion. If so, it allocates some, or all, of
that, and exits. That avoids any copying. In other cases it can
expand in front of the original, and copying is required, but the
memory locality is roughly preserved. If that also fails, we can
resort to the original malloc, copy, and free routine.

These decisions never involve searches, thus keeping calls O(1).