I followed the advice from Brighteyes, and also realised that I did know the upper limit of the new_word variable, so I've actually removed all explicit calls to malloc(). Here is the adjusted code...
Code:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "permutations.h"
void
permute( char *input,
char *pool )
{
char output[MAXLENGTH] = "";
char new_word[MAXLENGTH] = "";
int ctr, target, pool_len;
strcat( output, input );
target = strlen( output );
pool_len = strlen( pool );
for( ctr = 0 ; ctr < pool_len ; ctr++ )
{
output[target] = pool[ctr];
append_perm( output );
permute( output, extract_letter( pool, new_word, pool_len, ctr ) );
}
}
char *
extract_letter( char *word, char *new_word, int word_len, int letter )
{
int ctr;
for( ctr = 0 ; ctr < letter ; ctr++ )
new_word[ctr] = word[ctr];
for( ctr = letter ; ctr < word_len ; ctr++ )
new_word[ctr] = word[ctr+1];
return( new_word );
}
It is called from a main in another program file...
Code:
#include <stdio.h>
#include "permutations.h"
struct node *head_perm = NULL;
struct node *tail_perm = NULL;
int
main( int argc, char *argv[] )
{
if( argc != 2 )
{
printf( "\nUsage : andy <string>" );
return( 0 );
}
permute( "", argv[1] );
printf( "\n\n" );
return( 0 );
}
...and finally here is the top of the output from prof
Code:
%Time Seconds Cumsecs #Calls msec/call Name
48.5 28.36 28.36 _brk_unlocked
13.0 7.57 35.9379144928 0.0001 _mcount
11.7 6.82 42.75 9864101 0.0007 permute
4.6 2.70 45.45 9864100 0.0003 extract_letter
4.0 2.32 47.77 9864100 0.0002 malloc
3.7 2.19 49.9619728202 0.0001 strlen
3.7 2.17 52.13 realloc
3.0 1.75 53.88 9864100 0.0002 strcpy
2.5 1.44 55.32 9864100 0.0001 append_perm
2.3 1.33 56.65 9864101 0.0001 strcat
1.6 0.91 57.56 _free_unlocked
0.9 0.53 58.09 _fileno_unlocked
0.5 0.32 58.41 _libc_threads_interface
0.0 0.01 58.42 116050 0.0001 _sbrk_unlocked
0.0 0.01 58.43 116050 0.0001 _sbrk
As you can see, nearly two thirds of the excution time is taken up by _brk_unlocked and _mcount.
I don't want to try and do anything complicated with the memory, I was just wondering if you could see anything daft that I'm doing which might be unnecessary.
Thanks,
Andy