Competing criteria

N

nroberts

I'm having trouble figuring out how to get seemingly mutually
exclusive goals and criteria to work together.

The technical lead/architect for the project I'm on is from an
embedded background and therefore doesn't like heap allocation. I
don't know if this is a real issue in that domain, having never done
it myself, but that's what he's told me when complaining about my use
of allocated buffers and such. Factory like functions also seem to
upset him. I'm not so sure about function pointers, but every time
I've made something that wasn't of the direct call, stack or global
variable kind of design he's kind of freaked out on me.

At the same time he wants me to write reusable code and has previously
wanted me to make unit tests, though now I'm not even sure about that
since he won't even look at them.

I'm getting kind of pissed off to tell the truth, but I still want to
try.

I'm coming into a project where the best solution seems to be a
multithreaded service. It's basically a proxy for a soap server
created by a third party that we're making generic and less soapy in
order for our various products to use it. Some of the calls can take
a long time and writing it multithreaded allows us to use the gsoap
library without having to muck about to use it asynchronously as it
doesn't really support such use.

I created a prototype for this service in C++ using all the
allocation, RAII, polymorphism, etc...so I could get a clear picture
of the problem. Now I need to convert the design into C (I'm fairly
certain he's going to tell me to). Normally this would be fairly
easy, replace exception processing with error codes, rewrite std::list
and such for all the types I want to hold or to use void*...use opaque
types and createXXX() functions... I'm not doing anything
particularly incredible with the C++, it could almost as easily be C.
This kind of stuff doesn't fly here though.

I can create circular buffer stacks to handle things like my thread
pools instead of allocating stack nodes. I can just declare my opaque
types openly and have initXXX() functions. Etc...I think this kind of
thing would make the guy happy but I don't see how to do that while
also meeting another goal he's said I need to meet: make this thing so
that it's a generic architecture for any soap connecting proxy. I
can't think of how to do such circular buffer stacks for specific
types (because I can't allocate) and still write them in a way that
can be used in different ways.

How does one make reusable components without at least some generics
and heap allocations? When everything has to be a direct call, how do
you allow clients to override behavior? What are some idioms,
patterns, whatever that I can use to at least make some attempt at
getting both of these ideals to work together?
 
S

Seebs

I'm having trouble figuring out how to get seemingly mutually
exclusive goals and criteria to work together.
Heh.

The technical lead/architect for the project I'm on is from an
embedded background and therefore doesn't like heap allocation.

This is probably an obsolete view, but who knows? Anyway, the canonical
solution to "not heap allocation" is to define a reasonable maximum count
of simultaneous objects, statically allocate them, and then basically
write your own mini-allocator that keeps track of which ones you're using.

This, you will note, is probably stupid.

Note that either way, it is very important that you handle lack of
resources gracefully.

-s
 
J

John Gordon

In said:
At the same time he wants me to write reusable code and has previously
wanted me to make unit tests, though now I'm not even sure about that
since he won't even look at them.

He wants to ensure that adequate tests exist but doesn't care about the
gory details; that's not necessarily an unreasonable attitude for a project
lead.
 
S

Stefan Ram

nroberts said:
At the same time he wants me to

If he is contradicting himself, you cannot succeed. So to
ensure you are not blamed for his contradictions yourself,
you might consider asking him for his coding requirements
/in writing/.
I created a prototype for this service in C++ using all the
allocation, RAII, polymorphism, etc...so I could get a clear picture

Thinking in C++ and then translating to C will not always
give the best results.
How does one make reusable components without at least some
generics and heap allocations?

You can write generic code with preprocessor macros, but
will loose type safety in comparision to C++.

Sometimes, storage with dynamic storage duration can be
replaced by storage with automatic or static storage
duration (sometimes in an outer scope). This depends on the
details. One also can allocate a large chunk of storage of
static or automatic storage duration and then use one's
own custom heap implementation on top of this.

For example, study how TeX was implemented in Pascal.

»TeX does all of its dynamic allocation itself from
fixed-size arrays and uses only fixed-point arithmetic
for its internal calculations.«

http://en.wikipedia.org/wiki/TeX
When everything has to be a direct call, how do you allow
clients to override behavior?

Sometimes this can be replaced by switch statements,
but one will loose the advantages of an OOP-like style.
What are some idioms, patterns, whatever that I can use to at
least make some attempt at getting both of these ideals to
work together?

The best designs are based on the target language right from
the start. For example, when you design a typesetting system
for Java, no one will have fun then translating this to Pascal.
When a programmer with experience in Pascal, designs the
implementation for Pascal right from the start, it will be better.
 
R

Richard Damon

I'm having trouble figuring out how to get seemingly mutually
exclusive goals and criteria to work together.

The technical lead/architect for the project I'm on is from an
embedded background and therefore doesn't like heap allocation. I
don't know if this is a real issue in that domain, having never done
it myself, but that's what he's told me when complaining about my use
of allocated buffers and such. Factory like functions also seem to
upset him. I'm not so sure about function pointers, but every time
I've made something that wasn't of the direct call, stack or global
variable kind of design he's kind of freaked out on me.

At the same time he wants me to write reusable code and has previously
wanted me to make unit tests, though now I'm not even sure about that
since he won't even look at them.

I'm getting kind of pissed off to tell the truth, but I still want to
try.

I'm coming into a project where the best solution seems to be a
multithreaded service. It's basically a proxy for a soap server
created by a third party that we're making generic and less soapy in
order for our various products to use it. Some of the calls can take
a long time and writing it multithreaded allows us to use the gsoap
library without having to muck about to use it asynchronously as it
doesn't really support such use.

I created a prototype for this service in C++ using all the
allocation, RAII, polymorphism, etc...so I could get a clear picture
of the problem. Now I need to convert the design into C (I'm fairly
certain he's going to tell me to). Normally this would be fairly
easy, replace exception processing with error codes, rewrite std::list
and such for all the types I want to hold or to use void*...use opaque
types and createXXX() functions... I'm not doing anything
particularly incredible with the C++, it could almost as easily be C.
This kind of stuff doesn't fly here though.

I can create circular buffer stacks to handle things like my thread
pools instead of allocating stack nodes. I can just declare my opaque
types openly and have initXXX() functions. Etc...I think this kind of
thing would make the guy happy but I don't see how to do that while
also meeting another goal he's said I need to meet: make this thing so
that it's a generic architecture for any soap connecting proxy. I
can't think of how to do such circular buffer stacks for specific
types (because I can't allocate) and still write them in a way that
can be used in different ways.

How does one make reusable components without at least some generics
and heap allocations? When everything has to be a direct call, how do
you allow clients to override behavior? What are some idioms,
patterns, whatever that I can use to at least make some attempt at
getting both of these ideals to work together?

As someone who has written a number of embedded projects, I can give
some grounds for the desire to limit heap usage and where it can
reasonably be used and where it should not.

I typical embedded project can NOT make the common "hosted" assumption
of nearly unlimited memory being available. It also typically needs to
have a virtually infinite run time, so heap fragmentation needs to be a
concern.

The guidelines I tend to work with are:

1) Heap allocations at "start-up" are normally not an issue. If you
don't have the memory needed, you find out right away, not at some
unknown time in the future.

2) Critical tasks, that must be able to complete on a schedule may NOT
make further heap allocation, but only use statically allocated buffers
or buffer allocated at start-up.

2a) If a task only becomes "critical" after some other action that is
allowed to fail, that other action is allowed to allocate the resources
for the critical task, and must fail if it can't get them.

3) Non-critical tasks may be allowed to allocate dynamic resources, but
there should be points in the execution of the program where most of
these have been returned to the heap to clear up heap fragmentation.

With this, your program can be generic (at compile time), as hopefully
you can know which types are needed for this program, and you can then
preallocate the needed buffer set, but the code is still usable for
other applications that use different sets of types.

If you point out that you are only doing heap allocations at "startup"
time, (or for non-critical code tasks, that are allowed to fail/be
delayed), then he will hopefully be satisfied.
 
R

Roberto Waltman

Seebs said:
the canonical
solution to "not heap allocation" is to define a reasonable maximum count
of simultaneous objects, statically allocate them, and then basically
write your own mini-allocator that keeps track of which ones you're using.
This, you will note, is probably stupid.

Far from being stupid, that is the only way you can guarantee that
memory allocation will not fail due to memory fragmentation, in
systems with limited resources, no virtual memory and that must run
24/7.
 
R

Richard Damon

Far from being stupid, that is the only way you can guarantee that
memory allocation will not fail due to memory fragmentation, in
systems with limited resources, no virtual memory and that must run
24/7.

As I mentioned last night, that isn't totally true. It can be generally
considered safe to do heap allocation during initial startup (for
buffers that will then live forever, perhaps handed out and collected
with allocation functions.

While in principle, it would normally be possible to rewrite all the
code that uses the heap to use statically allocated buffers, this often
forces details of implementation to leak out, especially of objects that
need internal buffers that can't be fixed in size over all uses.

It can also be acceptable to heap allocations for non-critical
operations that are allowed to fail or be postponed for arbitrary
periods of time. These allocations should be for a limited period of
time, and it is desirable for there to be occasional times when most of
these are all released at the same time to let the heap defragment.
 
P

Phil Carmody

Roberto Waltman said:
Far from being stupid, that is the only way you can guarantee that
memory allocation will not fail due to memory fragmentation, in
systems with limited resources, no virtual memory and that must run
24/7.

False, and likely to fail in most embedded scenarios I've worked on.
Likely to fail, as if you have 100 units of RAM, and may need up to 20
of size 5, or 5 of size 20, but not simultaniously, then you must use
dynamic allocation.

And false, because if you never hand out pointers, but handles, then
you can use dynamic memory allocation and compact your heap either in
the background or on demand.

Phil
 
A

Ark

As I mentioned last night, that isn't totally true. It can be generally
considered safe to do heap allocation during initial startup (for
buffers that will then live forever, perhaps handed out and collected
with allocation functions.

While in principle, it would normally be possible to rewrite all the
code that uses the heap to use statically allocated buffers, this often
forces details of implementation to leak out, especially of objects that
need internal buffers that can't be fixed in size over all uses.

It can also be acceptable to heap allocations for non-critical
operations that are allowed to fail or be postponed for arbitrary
periods of time. These allocations should be for a limited period of
time, and it is desirable for there to be occasional times when most of
these are all released at the same time to let the heap defragment.

IOW, malloc() can be (made) more or less benign but free() is totally
unacceptable.
Which is not totally true either.
If memory serves me right, there are allocation algorithms that
guarantee to succeed if the contiguous memory pool is "only" twice as
large as the max you need at any given time. Of course if you already
know what this max is, you can probably do better w.r.t. memory resources.
OTOH, for any allocation algorithm there is a pattern of
allocations/deallocations which would fatally fragment the pool (aka
heap), in the sense that enough total memory is available but it is not
contiguous
- Ark
 
R

Richard Damon

On 10/22/2011 4:47 PM, Richard Damon wrote:

IOW, malloc() can be (made) more or less benign but free() is totally
unacceptable.
Which is not totally true either.
If memory serves me right, there are allocation algorithms that
guarantee to succeed if the contiguous memory pool is "only" twice as
large as the max you need at any given time. Of course if you already
know what this max is, you can probably do better w.r.t. memory resources.
OTOH, for any allocation algorithm there is a pattern of
allocations/deallocations which would fatally fragment the pool (aka
heap), in the sense that enough total memory is available but it is not
contiguous
- Ark

The rule I always use is a task is not allowed to fail, then it can't
call on anything that might fail. malloc, in general, has the
possibility to fail so needs to be avoided in tasks that can not fail.

free() is actually always safe, as free can never fail, and can never
cause another malloc to fail. What can get you in trouble is to free a
resource that you will need in the future, as after you free a memory
block, you can't be sure you can get it back until every block allocated
after it is freed too (based on normal heap rules).

While, as you say, there are patterns of allocations and deallocations
that fragment the heap, the rule that allocations (after the startup
code) are be of short/finite duration is designed it prevent those bad
patterns. Also, the goal to have periods of time when you free most of
the short term usage also minimizes how bad fragmentation gets.
 
A

Ark

The rule I always use is a task is not allowed to fail, then it can't
call on anything that might fail. malloc, in general, has the
possibility to fail so needs to be avoided in tasks that can not fail.

free() is actually always safe, as free can never fail, and can never
cause another malloc to fail. What can get you in trouble is to free a
resource that you will need in the future, as after you free a memory
block, you can't be sure you can get it back until every block allocated
after it is freed too (based on normal heap rules).

While, as you say, there are patterns of allocations and deallocations
that fragment the heap, the rule that allocations (after the startup
code) are be of short/finite duration is designed it prevent those bad
patterns. Also, the goal to have periods of time when you free most of
the short term usage also minimizes how bad fragmentation gets.

I don't think we disagree on anything.
By "free() is evil" I mean that a pattern of pre-allocating on start-up
is fine (but doesn't buy you anything if you don't care about keeping
the types opaque); anything else is risky.
<OT>
I believe the idea of malloc was driven by use cases of non-interactive
programs that run and end, whether succeeding or failing. I mean, like
grep. For a program that starts and never ends, be it an embedded
freestanding program or hosted service/daemon, malloc /interface/ is
suited exceptionally poorly. An intermediate group is indeterminately
long interactive programs, like office applications - but they, as we
know, *are* allowed to fail :)
</OT>
- Ark
 
J

Joachim Schmitz

io_x said:
i think some free() function can fail in the wrost way

Indeed free() can fail if cou give something not NULL which hasn't come from
malloc(), calloc() or realloc() or had been free()'d already, in which case
undefined behavoir occurs (and free() doesn't have means to report an error)

From a Linux man-page:
free() frees the memory space pointed to by ptr, which must have been
returned by a previous call to malloc(), calloc() or realloc(). Otherwise,
or if free(ptr) has already been called before, undefined behaviour occurs.
If ptr is NULL, no operation is performed.



Bye, Jojo
 
W

Willem

Joachim Schmitz wrote:
) io_x wrote:
)> "Richard Damon" <[email protected]> ha scritto nel
)> messaggio )>> On 10/22/11 5:33 PM, Ark wrote:
)>> The rule I always use is a task is not allowed to fail, then it
)>> can't call on anything that might fail. malloc, in general, has the
)>> possibility to fail so needs to be avoided in tasks that can not
)>> fail. free() is actually always safe, as free can never fail, and can
)>> never cause another malloc to fail.
)>
)> i think some free() function can fail in the wrost way
)
) Indeed free() can fail if cou give something not NULL which hasn't come from
) malloc(), calloc() or realloc() or had been free()'d already, in which case
) undefined behavoir occurs (and free() doesn't have means to report an error)

IOW: free() can only fail if there is a programming error.
OTOH: malloc() can fail because of external circumstances.


SaSW, Willem
--
Disclaimer: I am in no way responsible for any of the statements
made in the above text. For all I know I might be
drugged or something..
No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT
 
N

Nick Keighley

Indeed free() can fail if cou give something not NULL which hasn't come from
malloc(), calloc() or realloc() or had been free()'d already, in which case
undefined behavoir occurs (and free() doesn't have means to report an error)

From a Linux man-page:
free() frees the memory space pointed to by ptr, which must have been
returned by a previous call to malloc(), calloc() or realloc(). Otherwise,
or if free(ptr) has already been called before, undefined behaviour occurs.
If ptr is NULL, no operation is performed.

I wouldn't call this a failure on free()'s part. Essentially free()'s
pre-condition has been violated. The caller is the failure.
 
R

Richard Damon

[...]
The rule I always use is a task is not allowed to fail, then it can't
call on anything that might fail. malloc, in general, has the
possibility to fail so needs to be avoided in tasks that can not fail.

You may be using "fail" too broadly. Yes, malloc() can "fail" in
the sense that it reserves no memory. But malloc() does not then abort
the program or something equally drastic; it returns NULL to inform the
caller of the outcome and allow the caller to take action as appropriate
in the context. If the caller (and the caller's callers) cannot proceed
without the reserved memory, perhaps the program will then "fail" -- but
this is not an inevitable outcome when malloc() "fails."

If getenv("FAILURE_OPTION") returns NULL, is that a "failure?"

If strchr(string, '?') returns NULL, is that a "failure?"

If fopen("nonsuch.txt", "r") returns NULL, is that a "failure?"

Depending on the structure and needs of the program, the answers
could be any combination of "Yes," "No," and "It's complicated." The
same goes for malloc().

The simple answer is use the same definition of fail in the two places.
If the task isn't allowed to fail by aborting, but can say "can't do
it", then it can't call things that abort but can call things like
malloc which may return a "can't do it" response (as long as you check
for them and don't assume it gave you the memory). More commonly failure
is an inability to do the task requested. As you examples show,
sometimes what that really means is dependent on context.

As most guideline rules, it is stated in the simple, easy to remember
format, not with all the appended legalese about unusual conditions and
exemptions. As an example, a task that must complete, might be able to
call malloc for a buffer, if the task has a suitable alternative that it
can fall back on if the malloc returns no buffer, for example, maybe it
has a buffer kept in reserve, that it can use in emergencies, but when
it falls back on that, it sends out a notice that it may not be able to
handle any more traffic (allowing future requests to fail).
 
M

Malcolm McLean

if the task has a suitable alternative that it
can fall back on if the malloc returns no buffer,
People discuss this quite a bit. Technically it's often possible to
use a less memory-hungry algorithm if malloc() fails. However it's
almost never done in real code, because it means programs become much
more difficult to write and to test.
 
S

Seebs

Far from being stupid, that is the only way you can guarantee that
memory allocation will not fail due to memory fragmentation, in
systems with limited resources, no virtual memory and that must run
24/7.

True, but it doesn't prevent memory allocation from failing due to a lack
of resources. So you still have to deal with memory allocation failures.

And given a choice between rare failures due to fragmentation, and frequent
failures due to poor choice of static limits...

-s
 
M

Markus Wichmann

People discuss this quite a bit. Technically it's often possible to
use a less memory-hungry algorithm if malloc() fails. However it's
almost never done in real code, because it means programs become much
more difficult to write and to test.

It also means to write more code, some of which is almost never going to
get used... I mean, it would be like writing a program so that it runs
both on systems with an FPU and without: You basically have to write it
twice. It is almost always simpler to just say "Buy an FPU!" or "Buy
more RAM or enlarge the swap file!"

The correct separator would be dash-dash-space-newline, you are missing
the space.

HTH,
Markus
 
R

Richard Damon

True, but it doesn't prevent memory allocation from failing due to a lack
of resources. So you still have to deal with memory allocation failures.

And given a choice between rare failures due to fragmentation, and frequent
failures due to poor choice of static limits...

-s

If you have frequent failures, you didn't set your static limits
correctly. To do the static preallocations, you need to do analysis. You
need to define what is allowed to be active at any given time, an make
sure you have sufficient resources statically allocated to meet that
demand. if you can't do the analysis, you can't make the performance
guarantee. If you can't preallocate sufficient buffers to meet that
demand, you need to do one of the following:

1) Find a way to do some of the jobs with less memory.
2) Add more memory to the system.
3) Reduce the required guaranteed performance

If you switch to a dynamic allocation system, it is virtually impossible
to really guarantee a performance level, and it can look really bad for
you to have a device whose performance deteriorates over time and
requires periodic reboots to keep it working up to spec.

To have a allocation failure, because you are operating beyond your
spec, is NOT a system failure, it should be allowable for you to refuse
to process that request.

If you have some memory left over, you might want to switch to making a
heap request when your preallocated buffers are exhausted, in this case
since you are now allowed to fail, you are ok. When done, you should
know that THIS buffer should be returned to the heap and not one of the
other preallocated buffer to avoid heap fragmentation (and depending on
how you did it, the preallocated buffers may not have come from the heap).

Note, that it might be possible that you know that the system goes into
different "modes" where the types of buffers needed are different. This
can make preallocation a bit harder, but judicious use of unions can
often solve this. To the degree that you can't preallocate as
efficiently as you think you might be able to use the heap, consider
that the cost for getting the guarantee. To really be sure the heap will
work would add a LOT of stress testing and analysis, and even then there
will be some doubt. One way to think about it, which car would you buy,
the one guaranteed to be able to get up to 70 mph, and if conditions are
good a bit beyond that, or the car that if conditions are right will
surpass 100 mph, but they can't be sure if there might be cases, even
somewhat rare (like maybe driving for a few hours), where it will only
hit 45 mph. If I plan to be driving on the highway, I don't think I
would want that second car. It may even "on average" go faster, but when
I want the performance, I want it. In the same way, if I buy a system
with a spec, I want it to meet the spec, not occasionally come up short
needing a reboot to clear up its memory fragmentation.
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

Forum statistics

Threads
473,731
Messages
2,569,432
Members
44,832
Latest member
GlennSmall

Latest Threads

Top