Subject: Another Interesting Case Study: Permutations of a range of characters

From: Shlomi Fish <[email-masked]>
Date: Tue, 15 Jan 2002 03:48:10 +0200 (IST)

My apartment-mate approached me today, asking me to tell him how to write
a program in C. He said he was given a range of characters (say 'a' to
'z') and had to write all strings of length "len" that contains only those
characters. I wrote him the answer on a piece of paper, and he immidiately
wondered how he did not came up with it himself. So far he only studied
Intro to CS and SICP, and it is perhaps because string handling is not
covered very well in the SICP course or book.

I told him it was just tree recursion, and he quickly realized why.

Right now I set up to write the program in C, Perl and Haskell. Here are
my snippets:

ANSI C:
-------

#include <stdio.h>
#include <stdlib.h>

const char start_at = 'a';
const char end_at = 'e';

void recurse(char * buf, int len, int pos)
{
    if (len == pos)
    {
        printf("%s\n", buf);
    }
    else
    {
        char c;
        for(c=start_at;c<=end_at;c++)
        {
            buf[pos] = c;
            recurse(buf,len,pos+1);
        }
    }
}

void print_perm(int len)
{
    char * buf;
    buf = malloc(sizeof(len)+1);
    buf[len] = '\0';
    recurse(buf,len,0);
    free(buf);
}

int main(int argc, char * argv[])
{
    print_perm(3);

    return 0;
}

Perl:
-----

use strict;

my @myset_of_atoms = (map { chr(ord('a')+$_) } (0 .. 4));

sub print_perm
{
    my $len = shift;

    my $recurse;
    $recurse = sub {
        my $so_far = shift;
        if (length($so_far) == $len)
        {
            print "$so_far\n";
            return;
        }
        foreach (@myset_of_atoms)
        {
            $recurse->($so_far.$_);
        }
   };
   $recurse->("");
}

&print_perm(3);

Haskell:
--------

myset_of_atoms :: [Char]
myset_of_atoms = ['a'..'e']

myset :: Int -> [String]
myset 0 = [ "" ]
myset n = [ (a:as) | a <- myset_of_atoms , as <- (myset (n-1))]

myperms = myset 3

print_perms [] = return ()
print_perms (a:as) = do print a
                        print_perms as

main = print_perms myperms

My conclusions:
---------------

1. The Haskell program is very elegant, IMO. I find Haskell to be very
elegant many times. This time it took me a very short time to write it,
which could have been shorter had I remembered the I/O details.

However, while Haskell performs well for such short, elegant cases, I
believe it scales less well than Perl for more elaborate cases where many
things need to be taken into account. Muli's example was more so, but I
remember re-writing Quad-Pres
(http://vipe.technion.ac.il/~shlomif/quadpres/) in Haskell and it resulted
in a very messy and unmaintainable code.

2. The Perl program is also elegant. Perl treatment of strings as opaque
items can hinder one when he has to deal with characters one by one. I was
able to save two variables, by using Perl's length() function and by using
a closure, which I could not have done in C.

3. This time, I think even the C program came out very nicely, mainly due
to C's way of managing strings and characters. Nevertheless, it still
exhibits a much larger code than either the Haskell or Perl program. But
that's ANSI C for you...

BTW, does everybody understand the Haskell program? If not - I can explain
it.

Regards,

	Shlomi Fish

----------------------------------------------------------------------
Shlomi Fish        [email-masked]
Home Page:         http://t2.technion.ac.il/~shlomif/
Home E-mail:       [email-masked]

"Let's suppose you have a table with 2^n cups..."
"Wait a second - is n a natural number?"

---

From: Oleg Goldshmidt <[email-masked]>
Date: 15 Jan 2002 10:48:21 +0200

Shlomi Fish <[email-masked]> writes:

> elegant many times. 

I have heard the statement many times, but I have never found the time
to verify it myself, and I did not understand your code (through no
fault of yours) yet.

As for elegance, here is crude lisp (no efficiency pursued):

(defun add-char (str charset len)
  (if (= (length str) len)
      (print str)
    (dolist (c charset)
      (add-char (concatenate 'string str c) charset len))))

(defun perms (charset len)
  (add-char "" charset len))

(perms (list "a" "b" "c" "d" "e") 3)

I suspect that on this list even those who don't know lisp will not
have much trouble reading this code...

> [C - OG] still exhibits a much larger code than either the Haskell
> or Perl program. But that's ANSI C for you...

You need at least 2 lines more to make it proper ANSI C - the function
prototypes... ;-)

-- 
Oleg Goldshmidt | [email-masked] 
"If it ain't broken, it has not got enough features yet."

---

From: Shlomi Fish <[email-masked]>
Date: Tue, 15 Jan 2002 11:08:48 +0200 (IST)

> to verify it myself, and I did not understand your code (through no

In that case, I will explain it. Stay tuned.

> have much trouble reading this code...

It seems so. But I believe the (list "a" "b" "c" "d" "e") stuff could be
encapsulated in a (generate-range ) function. Listing all the atoms one by
one is very unmodular.

> You need at least 2 lines more to make it proper ANSI C - the function

I don't think I need prototypes if all the functions are in the same file
and always precede their use. I suppose I should have then declared them
as static, but it makes little difference as it is because it's a
standalone program.

Regards,

	Shlomi Fish

> To unsubscribe from this group, send an email to:
> [email-masked]
>
>
>
> Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/
>
>

---

From: Shlomi Fish <[email-masked]>
Date: Tue, 15 Jan 2002 11:21:03 +0200 (IST)

> myset_of_atoms = ['a'..'e']

A character is a scalar in Haskell, and .. is the range operator (in a
similar vain to Perl). myset_of_atoms is declared to be a linked list of
the characters that are going to be used as atoms.

> myset n = [ (a:as) | a <- myset_of_atoms , as <- (myset (n-1))]

A call to (myset n) returns a list of all the permutations of n
characters. Naturally for n == 0 there is only one string - the empty
string. For n > 1 myset calls itself recursively and performs a cartesian
product of the atoms followed by tall the string for n-1.

> [ (a:as) | a <- myset_of_atoms , as <- (myset (n-1))]

The [ expr | var1 <- list1, var2 <- list2 ] is kind of like a map
expression on steroids. What it does is:
foreach a (myset_of_atoms)
	foreach as (myset (n-1))
		Append (a:as) to the list
	end
end

In fact this construct can be taken further and include an arbitrary
number of lists, constraints on the var[i]'s etc.

Strings in Haskell are linked lists of characters. Since a is a character
and as is the string and since the : operator is equivalent to cons, we
get a larger string whose first character is a and the other characters
are as.

> myperms = myset 3

This associates myperms with all the permutations which are 3 chars long.

> print_perms (a:as) = do print a

print_perms take a linked list of strings and echoes it to the screen. A
call for it with an empty list ([]) does nothing, while a call for it for
a list whose head is a and tail is as, prints a and then calls print_perms
for the rest of the list.

(When dealing with linked lists in Haskell, one should remember that it is
a strongly typed language. Therefore, the list is fully linear since
it's impossible to determine the type of an S-expression.)

> main = print_perms myperms

This defines the main function to call print_perms on myperms which is the
list of permutations. Not absolutely necessarily when working with Hugs,
and I'm not sure it is the correct syntax with GHC.

Regards,

	Shlomi Fish

---

From: Oleg Goldshmidt <[email-masked]>
Date: 15 Jan 2002 13:19:05 +0200

> encapsulated in a (generate-range ) function. Listing all the atoms one by

One can improve the code in so many ways, but I was not going to think
about all the issues on the time scale of 1 minute. I said the code
was crude. My point was that even code that quick'n'dirty can be
easily made quite elegant in lisp.

You could have pointed out that "a", "b" etc are strings rather than
characters (as they should be), but I was not concerning myself with
that.

> as static, but it makes little difference as it is because it's a

It seems that you are right. I tend to compile with strict flags,
including -Wmissing-prototypes, so I got warnings (I compiled your C
code to verify that mine gives the same result), but it does look like
-Wmissing-prototypes goes beyond standard enforcement.

---

From: mulix <[email-masked]>
Date: Tue, 15 Jan 2002 14:28:18 +0200 (IST)

one nit pick, if i may [and even if i may not]:

the original c program contained a malloc(), witout checking of its
return value. did no one else notice this, or am i the only nit picker
in our midst? ;)
-- 
mulix

http://vipe.technion.ac.il/~mulix/
http://syscalltrack.sf.net/

---

From: Shlomi Fish <[email-masked]>
Date: Tue, 15 Jan 2002 14:36:22 +0200 (IST)

> easily made quite elegant in lisp.

Understood.

> characters (as they should be), but I was not concerning myself with

Hmmm, Intersting. If the atoms were strings in C, it would have made the
code a bit more crude. The Perl Code would have worked as is, from what I
can tell right now, and the Haskell one would have required a few
modifications.

Anybody volunteers to write a code based on a given set of
strings?

> -Wmissing-prototypes goes beyond standard enforcement.

I usually use just -Wall, so I did not encounter it. Are there any -W
flags that are not usually included in -Wall that can be of use to
help detect pesky bugs?

Regards,

	Shlomi Fish

---

From: Shlomi Fish <[email-masked]>
Date: Tue, 15 Jan 2002 14:42:31 +0200 (IST)

> return value. did no one else notice this, or am i the only nit picker

I would be a rich man if I had a Shekel for every time I used malloc (or
new or GlobalAlloc or any of their friends) without checking for their
return values. I believe one of the assumptions of working in a modern
UNIX environment (or Win32 or even DOS DJGPP, etc) is that one has enough
memory. I was once told that programmers complained that checking for
errors in their code, increased the number of lines in their programs by a
factor of 4.

If the only time one uses malloc it is to allocate 5 or 20 bytes, and it
fails, then checking if the return value is NULL, probably won't stop the
program from crashing anyhow.

I believe I am going to start another flamewar here, but who is John Galt?

Regards,

	Shlomi Fish

---

From: Adi Stav <[email-masked]>
Date: Tue, 15 Jan 2002 18:01:59 +0200

> Right now I set up to write the program in C, Perl and Haskell. Here are

I wrote something very similar a while ago that did not use 
recursion. I think non-recursive code in C has better chances at 
portability, efficiency and elegance. Comes out slightly shorter,
too. I apologize for the coding style:

#include <stdio.h>
#include <stdlib.h>

#define N 3
#define M 3

int main()
{
   int array[ N ];
   int i, j;

   memset( array, 0, sizeof array );

   for (;;) {
      for ( j = 0; j < N; j++ )
	 printf( "%d, ", array[ j ] );
      printf( "\n" );

      for ( i = N - 1; i >= 0 && array[ i ] == M; ) 
	 array[ i-- ] = 0;
      if ( i < 0 )
	 return 0;
      array[ i ]++;
   }

   return 0;
}

---

From: Adi Stav <[email-masked]>
Date: Tue, 15 Jan 2002 19:16:53 +0200

> program from crashing anyhow.

I completely agree with you. But then again, I don't.

Many applications developed in C (e.g., you'd never guess it, the one 
I'm working on now) are rather resource intensive, and at the same 
time need to have a certain degree of reliability and fault 
tolerance. It is perfectly reasonable for a specific function not to 
be able to perform its task due lack of memory, but it is not 
acceptable to bring down the entire process. Risking a later crash 
and wrong output is completely out of the question.

On the other hand, like you said, most small utilities and programs 
that do their job and quit (e.g., traditional UNIX pipe tools) 
would rather just quit if they can't do their job. Checking for 
malloc() error codes is a nuisance, but you have to do it anyway so
that you don't risk a later crash or wrong output.

What I thought the last time I pondered this was that it could have 
been ideal for UNIX to have a matching signal for every errno value, 
and a matching errno value for every signal, just like you have
for SIGPIPE/EPIPE. This way, the default action for an OOM condition
would be to quit with identifying exit status and error message, but 
programs that are able to handle this situation can just SIGIGN the 
signal and check for the errno value. 

Of course, functions that /cannot/ fail are really cool. One of my 
favourite things are new object initializers that let the caller 
place the new objects on their stacks or in their structs instead of 
malloc()ing by them internally.

---

From: Oleg Goldshmidt <[email-masked]>
Date: 15 Jan 2002 16:18:36 +0200

Shlomi Fish <[email-masked]> writes:

> I believe one of the assumptions of working in a modern
> memory. 

You can't be serious! Do that once in your code, provide an API to
your colleagues, and sooner rather than later someone will call your
code in a long loop without freeing (because they don't realize there
is malloc there) - and there goes your mission-critical system.

I did notice malloc there, but I thought it was not worth a comment.
besides, I didn't do any error checking in my lisp snippet, either.
I see I was wrong.

> I was once told that programmers complained that checking for errors
> in their code, increased the number of lines in their programs by a
> factor of 4.

You were _told_ that? I can attest to this - I tend to write many
short functions, return error codes, and check them - that is 4 lines
of error checking for each function call, and if you modularize
properly your code consists of function calls mostly, like

rc = funcall(args);
if (rc != success) 
{
   report_error(rc);
   clean_up()
   return rc;
}

In some cases you can get away with perror(); exit(), but I have
worked in environments where aborting was not an option, and the only
acceptable behaviour was to percolate the error all the way to the
top. Incidentally, I worked one in an environment where malloc was not
an option.

You can wrap typical error handling in a macro to reduce number of
code lines visually, so it will look like

VERIFY(funcall(args));

or sth like this. I also wrote elisp code to make emacs generate
error-handling code for me.

But you do not compromise on error handling, ever.

> who is John Galt?

Right, who is he?

---

From: Oleg Goldshmidt <[email-masked]>
Date: 15 Jan 2002 16:22:19 +0200

> flags that are not usually included in -Wall that can be of use to

Lots. Check the info pages. I usually use a poor man's lint like

#!/bin/sh

# gcc lint emulation

gcc -c \
    -W \
    -O2 \
    -pedantic \
    -ansi \
    -Wall \
    -Wtraditional \
    -Wshadow \
    -Wid-clash-32 \
    -Wpointer-arith \
    -Wcast-qual \
    -Wcast-align \
    -Wconversion \
    -Wstrict-prototypes \
    -Wmissing-prototypes \
    -Wmissing-declarations \
    -Wnested-externs \
    -Dlint \
    -D__NO_STRING_INLINES \
    "$@" -o /dev/null 

I don't quite remember now how this particular set of options was
settled upon, suggestions welcome.

---

From: mulix <[email-masked]>
Date: Tue, 15 Jan 2002 16:36:21 +0200 (IST)

> UNIX environment (or Win32 or even DOS DJGPP, etc) is that one has enough

that is such a bogus assumption that it's not even funny. tell me,
shlomi, is there a conceptual difference between a program that works
80% of the time, and a program that works 99% of the time? before you
answer, consider the 99% case and the 100% case...

> I was once told that programmers complained that checking for

so? what's better, verbose and *correct*, or short and *incorrect*? not
to mention that there are ways to make malloc always return a valid
memory region, if your problem space allows this.

> program from crashing anyhow.

there is an extermely large difference between a program which prints
"out of memory, sorry" and a program that dies with a sigsegv.

> I believe I am going to start another flamewar here, but who is John

you seem to be doing that a lot lately :P~~
-- 
mulix

---

From: mulix <[email-masked]>
Date: Tue, 15 Jan 2002 17:18:07 +0200 (IST)

> signal and check for the errno value.

incidentally, standard c++ allows you to do this to some extent. by
default, new() throws an exception if it cannot allocate memory. you can
catch and handle this exception, or you can let it take its default
action - quit. fwiw, you can also change the handler which is called
when new cannot allocate memory to perhaphs attempt and free more
memory. as mentioned above, the default handler throws an out of memory
exception.

> malloc()ing by them internally.

care to give an example? (i assume we're talking about c).

and functions that cannot fail really are cool. unfortunately, anything
that can go wrong, will go wrong ;)
-- 
mulix

---

From: Omer Musaev <[email-masked]>
Date: Tue, 15 Jan 2002 17:59:25 +0200

> -----Original Message-----
> From: mulix [mailto:[email-masked]]
> Sent: Tuesday, January 15, 2002 5:18 PM
> To: [email-masked]
> Subject: Re: [hackers-il] Re: Another Interesting Case Study:
> Permutations of a range of characters
> 

[ idea of Adi about sending a special kind of killing/catchable error 
  on bad allocation skipped ]
 
> memory. as mentioned above, the default handler throws an out 

s/incidentally/intentionally/

The bad thing is that older compilers could return NULL if new failed.
The good thing is that this behaviour is frowned upon, and is considered
a good thing. 

> care to give an example? (i assume we're talking about c).

Here is an example ( style comments go to /dev/null ).

typedef struct foo foo ;

struct foo 
{
   int goo ;
   int bar ;
} ;

void 
init_new_foo( foo *pfoo )
{
   pfoo->goo = 1 ;
   pfoo->bar = 2 ;
} 

int 
main( int argc, char *argv[] )
{
   foo gg ;
   foo *pgg = &gg ;
   foo *pdf = ( foo *)(malloc(sizeof(foo))) ;
   if ( pdf == NULL ) 
   {
       perror ( "It's ok. "
                "It is not an error. "
                "Besides, memory is cheap now, "
                "so maybe its time to purchase some more") ; 
   }
   init_new_foo ( &gg ) ; /* initialise gg on stack */
   init_new_foo ( pgg ) ; /* do the same - via explicit pointer */
   init_new_foo ( pdf ) ; /* initalise pdf - which was hopefully allocated
on heap */  
}

It is almost like in C++, with notable exception that it gives flexibility
only, no 
reliability. I mean that programmer is still have to check his mallocs (
--reliability ),
but now the same initialiser can be applied to new foo, with no regard to
way it was 
allocated.

> ------------------------ Yahoo! Groups Sponsor 
> ---------------------~-->
> Sponsored by VeriSign - The Value of Trust
> Pinpoint the right security solution for your company - FREE
> Guide from industry leader VeriSign gives you all the facts.
> http://us.click.yahoo.com/pCuuSA/WdiDAA/yigFAA/saFolB/TM
> --------------------------------------------------------------
> -------~->
>

---

From: mulix <[email-masked]>
Date: Tue, 15 Jan 2002 18:03:02 +0200 (IST)

> Here is an example ( style comments go to /dev/null ).

this is becoming a standard disclaimer on this mailing list ;)

>    init_new_foo ( pdf ) ; /* initalise pdf - which was hopefully allocated

neat - but...
this code can not work when the caller is not aware of the internal
structure (or at least size) of the object to be allocated. in other
words, we break modularity badly.
-- 
mulix

---

From: Oleg Goldshmidt <[email-masked]>
Date: 15 Jan 2002 20:54:04 +0200

mulix <[email-masked]> writes:

> and functions that cannot fail really are cool. unfortunately,
> anything that can go wrong, will go wrong ;)

And when that happens, garbage in / garbage out is not really
acceptable, but garbage in / intelligent error message out is.

---

From: Shlomi Fish <[email-masked]>
Date: Wed, 16 Jan 2002 09:14:35 +0200 (IST)

OK. I realize that in some programs one has to check every memory
allocation, etc. In programs like database servers, or other kind of
servers that can consume an unlimited amount of memory, you may be able to
run out of memory and then the program may crash. In this case, memory
checking is a necessity.

However, in a simple 30 lines program that prints the permutations of
[a-e]{$n}, this is not the case. It is possible that I got too used to
Perl et al. where the interpreter gracefully exits when an allocation
fails. So, I still think writing C programs without an error check for
every little thing you do, is sometimes a valid option. It all depends on
how much your users depend on it.

It reminds me that one of my items on the Freecell Solver task list is:

* Check for unmalloced data and if so gracefully exit.

Despite the fact that FCS consumes more memory as it runs, I did not check
for a NULL return anywhere. There's an option to limit it to a certain
amount of stored states, which is what should be done if it is used as a
library. But running

my-board-gen [seed] | fc-solve

Can actually cause fc-solve to die because a memory was not allocated. I'm
a bit afraid that such a thing will totally mess up my code, though.

Muli has been a little flamatory in his post, I believe. I suppose he is
as religious about malloc() return values as I am about using a
long and verbose namespace prefix. Oh well, I guess no programmer is free
of programming-related obsessions. And C tends to bring out the worst in
anybody.

Malloc() and friends are part of the reason why I so much prefer
programming in higher level languages over C. Writing C code is a rather
cleansing experience in the fact that you are working directly with the
elements of the computer. But because I'm lazy, impatient and hubris-ful,
I'll try to avoid it whenever possible.

Regards,

	Shlomi Fish

---

From: Shlomi Fish <[email-masked]>
Date: Wed, 16 Jan 2002 09:22:07 +0200 (IST)

> too. I apologize for the coding style:

A few notes:

1. Your snippet is nice and I am familiar with this technique. However, I
do think that my original code is more readable and legible than this
technique.

2. It is possible to even write recursive procedures without using
procedural recursion. This is done by using one's own dedicated stack and
incrementing and decrementing the current state in it.

In some languages (like COBOL or VHDL) which do not support procedural
recursion, it is necessary to do so. Even in C it is a good programming
practice. The reasons are:

a. If the amount of recursion is arbitrary, then it is possible your
process will otherwise run out of stack.

b. One can pre-empt and resume the recursive process in O(1) time,
compared to O(depth) time for a version that uses procedural recursion.

I wrote a so-called "Soft-DFS" code for Freecell Solver that was a
Depth-First Search scan that did not use procedural recursion. I must
testify that the code was very picky, and I had to correct a large number
of errors until it worked like it should.

--------

Your methodology of advancing to the next permutation is a slightly
different algorithm, than the one I proposed. But nonetheless it is a
valid way of doing things.

Regards,

	Shlomi Fish

---

From: Adi Stav <[email-masked]>
Date: Wed, 16 Jan 2002 12:31:41 +0200

> * Check for unmalloced data and if so gracefully exit.

Easy. Write your own shlomif_{m,c,re}alloc() wrappers that have 
exactly the same syntax, but instead of returning NULL do "perror(); 
exit();". Search and replace, and you're done. I think lots of 
projects do this.

Also, you can try to limit the number of malloc()s in your code. It's
not always feasible, but I find that on-stack buffers, inline 
structs, and alloca() (which cannot fail) are often useful.

---

From: Adi Stav <[email-masked]>
Date: Wed, 16 Jan 2002 12:46:50 +0200

> do think that my original code is more readable and legible than this

A matter of taste. I had the same discussion with Omerm at work; of
course recursion will appear more elegant to a LISPer. I'm not saying
the linear is better, but its advantages are mostly like those of C
itself -- if you choose C, it's probably for certain reasons, and 
those reasons are likely to also lead you to a linear solution.

> incrementing and decrementing the current state in it.

Of course. The advantage in this situation is that you have to 
maintain a "stack" in any case, which is the array, and you don't 
need any other state except what is already there.

---

From: Adi Stav <[email-masked]>
Date: Wed, 16 Jan 2002 13:15:29 +0200

> this is becoming a standard disclaimer on this mailing list ;)

Yup. Let me add another one: I hereby apologize to all the gurus on
this list for forcing them to read beginning programmers getting all
excited about obvious techniques.

> words, we break modularity badly.

Not the structure. Only the size. From a pure compiler's perspective,
yes, you are exposing the structure, but it's considered bad practice
to reach into structs when an abstraction framework is provided. You
can add an underscore before every symbol if you want to emphasize 
that, and if you're really paranoid you can even put lots of garbage
and random characters in the members' names and #define them into 
their real names in a private header file. I hear g++ does it for you 
automatically :) There are also other solutions.

The main problem is that when size changes, binary compability often
breaks. That's why I wanted struct sizes to be a link-time variables.
But people often just leave padding variables at the end of structs 
for future expansion.

---

From: Adi Stav <[email-masked]>
Date: Wed, 16 Jan 2002 13:15:55 +0200

> memory. as mentioned above, the default handler throws an out of memory

Well, of course. If you are using a language with exceptions then the
error handling situation is completely different.

> that can go wrong, will go wrong ;)

But not everything can go wrong to start with. getpid() can't fail, 
alloca() can't fail, a function call can't fail, a struct within a 
struct is always available if the bigger struct has been 
preallocated, and so forth. It's happened to me before that an API 
improvement of some infrastructure that changed a return value from 
"int" to "void" got propagated all the way up in the code in numerous 
places, whose functions also can no longer fail because their only 
points of failure were these infrastructure functions. This saved
hundreds LOCs in error checking.

---

From: guy keren <[email-masked]>
Date: Wed, 16 Jan 2002 10:38:10 +0200 (EET)

On Wed, 16 Jan 2002, Adi Stav wrote:

> not alwaysfeasible, but I find that on-stack buffers, inline

whats'cha talkin' about, willis? from alloca's man page:

RETURN VALUES
       The  alloca function returns a pointer to the beginning of
       the allocated space.  If the  allocation  failed,  a  NULL
       pointer is returned.

ofcoruse it can fail - what if allocating space on stack requires mapping
an unmapped page, and thre's no more memory overall on the system for
that?

--
guy

"For world domination - press 1,
 or dial 0, and please hold, for the creator." -- nob o. dy

---

From: guy keren <[email-masked]>
Date: Wed, 16 Jan 2002 10:44:45 +0200 (EET)

> run out of memory and then the program may crash. In this case, memory

indeedi doody.

> how much your users depend on it.

its more then this. when one runs your program, they might run out of
memory because they had little memory to begin with (e.g. some _other_
program has run loose and is consuming lots of memory, but it so happens
that just when _your_ program tried to allocate memory, the machine's heap
ran out.

what users get is random crashes which they cannot explain.

> a bit afraid that such a thing will totally mess up my code, though.

i'm glad for you muli didn't read your FCS code, then ;) and that i didn't
read it either. not that i always remember to check malloc's return value,
but i do try to do that.

> of programming-related obsessions. And C tends to bring out the worst in

you're comparing oranges with apples. one can bite you at
development/compile time - i.e. as a programmer. the other is likely to
bite you at runtime - i.e. as a non-suspecting user. different impacts.

> I'll try to avoid it whenever possible.

ok. why don't you then switch to java? you'll love working with its
garbage collector ;)

--
guy

---

From: "Nadav Har'El" <[email-masked]>
Date: Wed, 16 Jan 2002 11:22:06 +0200

> exit();". Search and replace, and you're done. I think lots of 

Right. Ever since I saw John Ousterhout do that in his Tcl's sourcecode,
I've been using this trick in all major programs I write. It doesn't work
well for libraries, or other cases when exiting the program is not the proper
thing to (so if exiting is not ok, use C++ exceptions or C longjumps).

It also adds a bit of time overhead to every malloc call - but if you code
well you don't use billions of tiny malloc requests anyway, right? :)

-- 
Nadav Har'El                        |    Wednesday, Jan 16 2002, 3 Shevat 5762
[email-masked]             |-----------------------------------------
Phone: +972-53-245868, ICQ 13349191 |ech`echo xiun|tr nu oc|sed
http://nadav.harel.org.il           |'sx\([sx]\)\([xoi]\)xo un\2\1 is xg'`ol

---

From: Oleg Goldshmidt <[email-masked]>
Date: 16 Jan 2002 11:28:16 +0200

Shlomi Fish <[email-masked]> writes:

> [a-e]{$n}, this is not the case. 

Agreed, given that the only purpose of that program was to present
different implementation of a simple algorithm on this list. Yhat is
why I glanced over malloc() in the posted snippet without saying a
word, or, indeed, thinking twice about it. However,

> It all depends on how much your users depend on it.

so do be careful about error checking in any code likely to be used,
however short it is. In a couple of years you might need this
algorithm as a part of a larger project, and you will be tempted to
cut'n'paste the code from hackers-il archive...

There is an issue of good habits and practices and not getting used to
cutting corners, but I have already stated my beliefs on this matter
earlier on this list, cf.

http://groups.yahoo.com/group/hackers-il/message/1062

---

From: Oleg Goldshmidt <[email-masked]>
Date: 16 Jan 2002 17:02:26 +0200

"Nadav Har'El" <[email-masked]> writes:

> On Wed, Jan 16, 2002, Adi Stav wrote 

> I've been using this trick in all major programs I write. 

Another example is Steven's code in all of his books.

> It doesn't work well for libraries, or other cases when exiting the
> program is not the proper thing to (so if exiting is not ok, use C++
> exceptions or C longjumps).

I am not sure longjumps are that good an idea. When exiting is not
allowed, I prefer propagating an error code to the caller. You can
wrap your function calls in a macro (which is not ideal, either).

---

From: Adi Stav <[email-masked]>
Date: Wed, 16 Jan 2002 20:11:22 +0200

>        the allocated space.  If the  allocation  failed,  a  NULL

Silly me, I looked in the Solaris man page which mentions no such
possibility of failure. glibc and BSD say they can fail, indeed.

> an unmapped page, and thre's no more memory overall on the system for

I don't think it's that obvious.

I'd expect that libc will still not be able to know about it. I 
think extending the stack, unlike extending the heap, involves no 
system calls -- it's the kernel that knows it, asynchronously 
relative to the userspace code. After all, you don't get an error
status for "char buf[4*1048576*1048576]" either, so there's nothing
to check. This is the same as the famous OOM situation in Linux.
For this reason, I wouldn't be surprised to discover that glibc and
BSD can't fail either even though they say they can. I tried it on
my plain vanilla i386 RedHat 6.2, and alloca() never fails -- it 
either succeed or segfaults. The limit appears to be 8MB per stack 
frame, regardless of whether it comes from alloca() or the compiler.

---

From: "Nadav Har'El" <[email-masked]>
Date: Wed, 16 Jan 2002 17:23:10 +0200

> frame, regardless of whether it comes from alloca() or the compiler.

When we're talking about a single-threaded process (on Linux), this 8MB (on
Linux 2.4) is simply the ulimit (see ulimit -s) your process has set. You can
theoretically increase this limit to fill up whatever virtual memory you have.

In multithreaded applications (again in Linux, and glibc's Linux Threads),
the situation is a bit more complicated. Linux can no longer grow a huge stack
from the other end of the virtual memory space, and must set up space in
virtual-address space for each thread's stack (stacks must be contiguous in
virtual memory). So if your 'ulimit -s' is set to to 8MB, and you have 10
threads, don't be surprised if your process seems to take up 80MB of virtual
memory! (of course, most of it will not be swapped in because most of these
huge stacks are never used). Morals: when running a multithreaded application,
don't use huge 'ulimit -s'. I always explicitly set the stack size limit
in Linux Threads programs (before calling pthread_spawn() - tell me if anyone
is interested in a code snippet).

If you program in the kernel you're much more limited: in Linux 2.2 (for
example), the kernel stack is 2 pages (8192 bytes, on i386) long. That's it!
If you create a large automatic variable, abuse recursion or alloca, you
simple overflow the stack and you'll never know about it - until your kernel
starts doing weird things :(

-- 
Nadav Har'El                        |    Wednesday, Jan 16 2002, 3 Shevat 5762
[email-masked]             |-----------------------------------------
Phone: +972-53-245868, ICQ 13349191 |A diplomat thinks twice before saying
http://nadav.harel.org.il           |nothing.

---

From: mulix <[email-masked]>
Date: Wed, 16 Jan 2002 17:30:35 +0200 (IST)

> example), the kernel stack is 2 pages (8192 bytes, on i386) long. That's it!

same thing in 2.4, afaik. and in practive it's less, since each task's
task_struct lives at the bottom of the task's stack, taking up ~790
bytes.

> starts doing weird things :(

kernel programming - if it's predictable or reproducible, it's boring ;)
-- 
mulix

---

From: Adi Stav <[email-masked]>
Date: Wed, 16 Jan 2002 22:48:51 +0200

> theoretically increase this limit to fill up whatever virtual memory you have.

Ahh, so that's why it's so reproducible. I didn't think of checking 
ulimit -- I assumed that since I didn't limit it, everything was 
unlimited. This proves my point though -- even in the most obvious
of cases, alloca() failed to fail.

> is interested in a code snippet).

GNU/Linux's (and Solaris's) malloc() don't do any actual allocation;
They are O(1), and the only wasted resource for malloc()ed but unused
memory is address space, which will not be an issue unless you use 
hundreds of threads. Neither RAM nor swap are used.

> starts doing weird things :(

Kernel environment is so different that I'd expect every code ported
to it to go at least some auditing. Intensive stack use will also 
give trouble to e.g. embedded or special systems. alloca() is not a
very portable function. But if you know your code is going to run on
a UNIX/NT type system, it can be useful.

---

From: Shlomi Fish <[email-masked]>
Date: Wed, 16 Jan 2002 20:07:33 +0200 (IST)

> ok. why don't you then switch to java? you'll love working with its

I take that you meant what you said, and are not sarcastic. OK - Java is a
very nice language. Looks like C++, behaves much the same and has garbage
collection. From what I heard (and can imagine) it's very clean,
consistent and fun, at least until you get those random crashes.

The only really serious thing I did in Java is MikMod for Java, in which I
took an existing ANSI C code and gradually converted it to JDK 1.0.2
(which I believe is deprecated). I did not do it too well, from many
reasons, but the code works, or at least used to work on that JDK.

If I'm looking for a C-look-alike with GC I'll probably turn to Java (or
to C# assuming the DotGNU/Mono stuff gets through). There are several
disadvantages to Java, however:

1. Technical ones: it crashes a lot.

2. Licensing ones: Sun is killing Java with the way it develops it. I'm
not saying it should be 100% open-source, but everything should be at
least a project with a collaborative feel about it. (i,e: a public CVS
server, mailing lists for developing the core components, etc.)

3. Philosophical ones: it still gives me a higher level of abstraction
than C. It's not just C with garbage collection - it's a whole new ball
game with lots of APIs and abstraction.

I usually prefer Perl over Java because I get a lot of cool primitives for
doing common tasks, and because I find Perl's syntax and grammar much more
natural than Java's. Larry Wall has written an article in which he
explains how he tried to embed natural language principles in Perl:

http://www.wall.org/~larry/natural.html

I think he did a marvelous job, because Perl programming is more natural
to me than any other language.

(Please don't turn it into a Java vs. Perl war)

When I encounter a Java project in Freshmeat, I usually don't take a
second look. (you make the deduction why). I plan to translate the
Freecell Solver code to Java because I think it would be really cool if
people can browse into a web-site and have there a Freecell implementation
that solves Freecell using my algorithm as an applet. And converting it to
Java seems inevitable because Java is the de-facto standard.

---

In any case, for those of you who have followed Parrot development, they
recently added JIT for x86. This may eventually make it possible to write
code in Perl et al. and run it almost as fast as C. Now - that would be
call, IMO. (although Muli would again disagree with me because he
specifically told me he much prefers C over Perl or Python) As someone who
wrote very large programs in Perl, I can really appreciate its scalability
(in maintainability not in speed - :-)), modularity and effort/code ratio.

Do you think JIT is the reason Java code tends (or at least tended) to
crash so much? From my impression JIT is a can of worms. Parrot would
still have an option of running without JIT, an option which I would
prefer on code that I rely upon.

---

There are other approaches to tackle the dillema of speed vs. high-level
abstractions:

1. Internet C++ -
http://ivm.sourceforge.net/

a high level bytecode that has a gcc backend SPEC, and so can have code in
any language that uses the gcc backend. (and a previous thread on the
subject here counted 10 or 11 of them, IIRC). The code is not supposed to
crash the process, but rather the interpreter would detect that the
program made something it was not supposed to do - free its relevant
memory - and exit.

Naturally, there's gcj which can compile Java code (or bytecode) to
machine language, and there you have garbage collection.

(If IVM was the standard, then converting my code to Java would have been
a non-issue. I don't know how much progress those IVM guys did.)

2. Compiling Higher-Level Languages

I personally much prefer interpreters over compilers, despite the fact
that they are slower. I just prefer saying "perl test.pl" instead of "make
" and then "./test" and "gdb ./test" etc.

However, I do suppose having an interpreter and a compiler for the same
language is a good idea. An example for this is Dylan, which I did not
test yet but hear about. A bad example is Haskell in which the common
interpreter - hugs - is not compatible with the most common compiler -
GHC. And there are other compilers and interpreters, but they are not
compatible with each other. If you do simple things in Haskell, they can
be done everywhere, but beyond that - you'll encounter a lot of
incompatibility.

The Haskell community is not focused enough on dealing with Haskell's
child diseases. Right now the situation is that GHC is written in Haskell,
and is the only compiler that can compile itself. It contains a lot of
interesting APIs, but most of them are not available in Hugs, which is
much faster and easier to use. All the other Haskell compilers are written
in Haskell or something similar too.

A common theme in the Haskell mailing lists is: FP rules! Strong-Typing
Rules! Haskell Rules! But meanwhile there are technicalities that prevent
it from becoming mainstream. What a shame. Hopefully, someone will code a
Haskell front-end to Parrot and then it will finally be truly useful. Or
maybe the Haskell community will come to its senses.

There's a similar situation going on with Scheme, IMO. Why do the Scheme
Request For Implementations do not contain standarized interfaces for such
useful things as sockets, random-access file operations, regexps etc? The
only Scheme implementations I found that came close to Perl with taking
CPAN account were Scheme/Tk and Guile. And in Stk a socket server example
(which came with the distro) segfaulted the interpreter.

My point is that the strength of a chain is the strength of the weakest
link and sometimes languages can fail or not gain momentum from purely
technical reasons.

Regards,

	Shlomi Fish

---

From: "Nadav Har'El" <[email-masked]>
Date: Wed, 16 Jan 2002 22:33:24 +0200

> of cases, alloca() failed to fail.

By the way, if you want to catch an alloca() failure, i.e., a stack overflow,
you can catch the SIGSEGV signal and then check if the calling function is
alloca() (or whatever gcc's internal function is named). This may not
work on multithreaded applications, as in that case the multiple threads'
stacks are all layed one after another, and overflowing one will just ruin
the other, without generating a page fault. (maybe they put one unmapped
page between each stack? that would make it easier to catch stack overflows
in multithreaded applications. It's been a while since I read the linuxthreads
code...).

> hundreds of threads. Neither RAM nor swap are used.

Sorry, its becoming too hard to follow the weekly changes in Linux's virtual
memory system for me to know if you're right or not.

I thought that in Linux when pages are mapped (and each of these 8MB need
to be mapped to something, so when it is finally used the kernel will know
what to do with it) swap-space was automatically assigned to it. I thought
it doesn't cause a 8MB write to disk, but that it does cause Linux to mark
8MB less swap space as available.
But maybe I'm wrong, or maybe swap "overcommitment" was added in 2.4, or
maybe this is the way those "pot smoking hippies in Berkeley" (to use
Linus' words) used to have it ;) I assume the most modern way is to map all
those stack pages to the same physical page (probably filled with zeros),
and mark those pages COW (copy-on-write), so that when the kernel gets a
page-fault on the first write to each such page, only then a fresh, seperate
page is set up. But then you'll need to deal with random applications dying
suddenly, because memory they successfully allocated long ago is suddenly
found not to be really available (i.e., the COW doesn't find a place to put
this new copy!).

If I remember OSF/1 (a.k.a. Digital Unix or Tru64) allowed you to choose
either one of these modes. The mode unlike what you described allowed for
a more stable system (no chance of random applications dying - applications
can only fail when calling malloc(), not later) but required more swap
space on average (because some swap needed to be "comitted" without actually
being used).

While on the subject, does anybody know a good book about the design of
the Linux 2.4 kernel? Not about writing device drivers, but rather about
the design of the virtual memory, VFS, scheduling, SMP, TCP/IP, and other
low-level stuff like that? "The design and implementation of 4.4BSD" has
been on my wishlist for a long time - maybe it's time I get it... I read
a few books about the design of UNIX long ago, but I don't remember much and
much has also changed since.

-- 
Nadav Har'El                        |    Wednesday, Jan 16 2002, 4 Shevat 5762
[email-masked]             |-----------------------------------------
Phone: +972-53-245868, ICQ 13349191 |The trouble with political jokes is they
http://nadav.harel.org.il           |get elected.

---

From: Adi Stav <[email-masked]>
Date: Thu, 17 Jan 2002 02:20:53 +0200

On Wed, Jan 16, 2002 at 10:33:24PM +0200, Nadav Har'El wrote:
> alloca() (or whatever gcc's internal function is named). 

Eww, extra kludgy. I don't really want to do that... alloca() by its 
very nature is supposed to be used for temporary buffers. If I have
close to 8MB on the stack, then there's no way to know in advance if
the straw that will break the camel's back will be an alloca() or a
function call. In any case we are talking about something deeply 
wrong with my code, and not a "user error" such as an out-of-memory
situation. I prefer a consistent core file. Nice trick, though.

I don't see alloca() as a replacement for malloc(), but for static 
buffers. By the way, C99 standardizes dynamically sized arrays on 
the stack -- but I can't think of an elegant implementation of 
those, no way. Does anyone have an idea what a C99 implementation 
is supposed to do? Are they just syntactic sugar over a pointer on
the stack and an alloca()? If so, I'd rather have an alloca()-like 
keyword... 

> 8MB less swap space as available.

Ahh, I see what you mean. Using large thread stacks takes no actual 
resources, but it might reserve those resources. I always have huge 
swap files just so that I only have to worry about /actual/ memory 
usage. After all, 10 threads will only take 80MB. It could have been 
so nice for Linux to support implicit secondary and tetriary swap 
areas on half-empty filesystems, unused inodes, on NFS, behind the 
sofa and so forth just so that it has some to use in case it has to, 
and the user doesn't have to worry about it.

> found not to be really available (i.e., the COW doesn't find a place to put

Hence the infamous OOM killer, whose overcomplicated heuristics 
always have it go after your innocent top instead of the frothing-
in-the-mouth rogue web app.

---

From: "Nadav Har'El" <[email-masked]>
Date: Wed, 16 Jan 2002 23:49:22 +0200

> the stack and an alloca()? If so, I'd rather have an alloca()-like 

It's been a while since I dabled in reading (VAX) assembly-language
compiled from C, so I might be wrong, but here is what I understand about
stacks:
you usually keep a "stack pointer" SP, which is probably a register on your
CPU.  if you have a function looking like

int f(int size){
	int j;
	char vec[size];
	char xyz[size];
...

Then, C replaces uses of "size" with *(SP-0) (your CPU might have a special
addressing mode for this, so no need for explicit addition and dereference),
"j" with *(SP-4), "vec[7]" with *(SP-(4+7)) and "xyz[7]" with *(SP-(4+size+7)).

[note that the details for i386 assembly are probably different - I never
bothered with learning it, unfortunately - VAX and C64 assembly were more
than enough for a lifetime ;)]

Also, when you call a function, you need to add the two "size"s to the
space you reserve on the stack.

-- 
Nadav Har'El                        |    Wednesday, Jan 16 2002, 4 Shevat 5762
[email-masked]             |-----------------------------------------
Phone: +972-53-245868, ICQ 13349191 |He who dies with the most toys is still
http://nadav.harel.org.il           |dead -- Citibank billboard, Manhattan 2001

---

From: "Orna" <[email-masked]>
Date: Thu, 17 Jan 2002 08:28:40 +0200

"code well".
there is no black and white here. so how would you estimate the amount of
unaccessible memory due to tiny malloc requests? (based on their size and as
a function of the number of times that malloc is used)?
Orna.
----- Original Message -----
From: "Nadav Har'El" <[email-masked]>

---

From: Adi Stav <[email-masked]>
Date: Thu, 17 Jan 2002 12:14:22 +0200

> "j" with *(SP-4), "vec[7]" with *(SP-(4+7)) and "xyz[7]" with *(SP-(4+size+7)).

But what do you do when you have three or four or ten dynamically-
sized arrays each with their own sizes that are based on variables
that have since changed? What if "size" changed in your code example?
The only way I can think of is for the compiler to keep somewhere 
pointers to the arrays, possibly kept as offsets from SP, of which 
your suggestion is a private case.

---

From: "Nadav Har'El" <[email-masked]>
Date: Thu, 17 Jan 2002 14:08:04 +0200

> a function of the number of times that malloc is used)?

Well, the answer to your question is obviously implementation-dependant.
Malloc can be written to have a zero (or more genrally, O(1)) space overhead
for N tiny requests (I did it several times, in several applications I wrote
which needed to allocate and free many tiny objects; The basic idea is to
keep a linked list of free objects of a certain size, and put the pointer *on*
the object when it's free, so that the linked list doesn't have any overhead).

It's possible to write an allocation algorithm that has a nearly-zero space
overhead for any size of requests (the usual definition is: say you allocated
a total of M bytes; you want to be sure that for a small epsilon, malloc
doesn't need to request from the system more than M*(1+epsilon) bytes).
There are many other issues in writing a good allocator, like time
(searching the heap for empty space needs time), support for multiple
threads, prevention of "fragmentation" of the heap (where tiny allocated
fragments prevent the allocation of a large block), and so on.

If you're interested in memory allocation, you might want to take a look
at the rather eleborate (78 page) "Dynamic Storage Allocation: A Survey and
Critical Review", by Wilson, Johnstone, Neely and Boles (Proceedings of 1995
International Workshop on Memory Management) - google for it or ask me if
you're interested.

Anyway, the inefficiency in many tiny mallocs I was talking about wasn't
the space inefficiency, but rather the time inefficiency: if you're
allocating millions of 4-byte objects (each allocation needs an malloc
call, which even in the best case involves at least a function call), you're
probably better off to rewrite the program to use one large array. In
some cases you can't, but in some cases you can and the millions of tiny
mallocs are simply a bad design decision. There are other inefficiencies
involved with having a million tiny objects instead of one array, like no
locality of memory access (slowing down a loop over all these objects) and
needing to derefrence pointers.

P.S. If I understand correctly, the glibc malloc is based on Doug Lea's
code (search for dlmalloc) modified by W. Gloger for multithreaded
applications (search for ptmalloc; if anyone is interested in more details,
I can point you to more papers and implementation notes).

-- 
Nadav Har'El                        |     Thursday, Jan 17 2002, 4 Shevat 5762
[email-masked]             |-----------------------------------------
Phone: +972-53-245868, ICQ 13349191 |And now for some feedback:
http://nadav.harel.org.il           |EEEEEEEEEEEEEEEEEEEEEEEEEEE

---

From: Oleg Goldshmidt <[email-masked]>
Date: 27 Jan 2002 22:38:04 -0500

Shlomi and others who offered solutions for listing 
character string permutations in different languages, and those who
amused themselves following that thread, might find 

http://www.bagley.org/~doug/shootout/

interesting. I just found it catching up on comp.lang.lisp. My
understanding is that the site is no longer actively maintained.

Check out the useful links list at the bottom. Perl lovers will
find 

http://pleac.sourceforge.net/

amusing, I guess.

-- 
Oleg Goldshmidt | [email-masked] 
If it aint't broken it hasn't got enough features yet.