Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c > #161968 > unrolled thread

Allocate length of word vs fixed length

Back to article view | Back to comp.lang.c

Contents

  Allocate length of word vs fixed length dfs <nospam@dfs.com> - 2021-07-19 12:50 -0400
    Re: Allocate length of word vs fixed length Bart <bc@freeuk.com> - 2021-07-19 19:01 +0100
      Re: Allocate length of word vs fixed length dfs <nospam@dfs.com> - 2021-07-19 14:29 -0400
        Re: Allocate length of word vs fixed length Bart <bc@freeuk.com> - 2021-07-19 19:49 +0100
          Re: Allocate length of word vs fixed length dfs <nospam@dfs.com> - 2021-07-19 18:01 -0400
            Re: Allocate length of word vs fixed length Bart <bc@freeuk.com> - 2021-07-19 23:25 +0100
        Re: Allocate length of word vs fixed length scott@slp53.sl.home (Scott Lurndal) - 2021-07-19 20:00 +0000
          Re: Allocate length of word vs fixed length Branimir Maksimovic <branimir.maksimovic@gmail.com> - 2021-07-19 23:29 +0000
        Re: Allocate length of word vs fixed length Real Troll <real.troll@trolls.com> - 2021-07-20 00:30 +0100
          Re: Allocate length of word vs fixed length DFS <nospam@dfs.com> - 2021-07-19 20:40 -0400
            Re: Allocate length of word vs fixed length Real Troll <real.troll@trolls.com> - 2021-07-20 17:00 +0000
        Re: Allocate length of word vs fixed length Kaz Kylheku <563-365-8930@kylheku.com> - 2021-07-24 01:07 +0000
    Re: Allocate length of word vs fixed length David Brown <david.brown@hesbynett.no> - 2021-07-19 21:35 +0200
      Re: Allocate length of word vs fixed length dfs <nospam@dfs.com> - 2021-07-19 18:02 -0400
    Re: Allocate length of word vs fixed length Ike Naar <ike@rie.sdf.org> - 2021-07-19 21:11 +0000
      Re: Allocate length of word vs fixed length dfs <nospam@dfs.com> - 2021-07-19 18:03 -0400
        Re: Allocate length of word vs fixed length Ike Naar <ike@sdf.org> - 2021-07-20 05:28 +0000
    Re: Allocate length of word vs fixed length dfs <nospam@dfs.com> - 2021-07-19 18:21 -0400
      Re: Allocate length of word vs fixed length Bart <bc@freeuk.com> - 2021-07-19 23:29 +0100
        Re: Allocate length of word vs fixed length dfs <nospam@dfs.com> - 2021-07-19 18:40 -0400
    Re: Allocate length of word vs fixed length Peter 'Shaggy' Haywood <phaywood@alphalink.com.au> - 2021-07-20 11:44 +1000
    Re: Allocate length of word vs fixed length Real Troll <real.troll@trolls.com> - 2021-07-20 22:15 +0000
      Re: Allocate length of word vs fixed length dfs <nospam@dfs.com> - 2021-07-20 20:22 -0400
        Re: Allocate length of word vs fixed length dfs <nospam@dfs.com> - 2021-07-21 23:23 -0400

Page 1 of 2  [1] 2  Next page →

#161968 — Allocate length of word vs fixed length

Loaded a list of words into an array.

The 370103 words came from https://github.com/dwyl/english-words
file = words_alpha.txt

Tested a couple memory allocation 'strategies' during loading:

1. allocate the strlen() of each word
2. allocate a fixed length (len of longest word = 32)

I figured getting strlen(word) each time would be slower than allocating 
a fixed amt of memory, but that wasn't the case.

Strategy 2 is significantly slower, and uses nearly 3x the memory.

Also, does anyone have any 'tricks' to make such a file load routine 
faster/more efficient?  Thanks

===========================================================
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

#define maxlen 32

//removes trailing isspaces and quote marks
char *rtrim(char *str)
{
	int len = strlen(str);
	while(len>0 && (isspace(str[len-1]) || str[len-1] == '\"'))	{len--;}
	str[len] = '\0';
	return str;
}


int main(int argc, char *argv[])
{	
	
	
	//vars
	int  i = 0, lines = 0;
	char word[maxlen] = "";
	char wordin[maxlen] = "";


	//open file, count lines
	FILE *fwords = fopen(argv[1],"r");
	while(fgets(wordin,sizeof wordin,fwords)!=NULL) {lines++;}
	
	//Geany adds a line feed to the very last line, so the true
	//line count is overstated
	lines -= 1;
	
	//mem
	char **words = malloc(sizeof(char*) * lines);
	
	
	//add words to array
	int memoption = atoi(argv[2]);
	int memlen = 0, memtotal = 0;
	rewind(fwords);
	while(fgets(wordin,sizeof wordin,fwords)!=NULL)
	{	
		
		strcpy(word,rtrim(wordin));
		
		//different memory allocations
		if(memoption==1)
		{memlen=strlen(word);}
		else
		{memlen=maxlen;}
		
		words[i] = malloc(sizeof(char*) * memlen);
		memtotal += memlen;
		
		strcpy(words[i],word);
		
		//printf("%d. '%s' ",i,words[i]);
		i++;
	}
		
	fclose(fwords);
	printf("\nloaded %d words\n",i-1);
	printf("\nFirst and Last words = '%s', '%s'\n",words[0],words[i-1]);
	printf("malloc option %d, total memory %d\n",memoption,memtotal);
	free(words);
	return(0);
}	
===========================================================

[toc] | [next] | [standalone]

#161969

On 19/07/2021 17:50, dfs wrote:
> Loaded a list of words into an array.
> 
> The 370103 words came from https://github.com/dwyl/english-words
> file = words_alpha.txt
> 
> Tested a couple memory allocation 'strategies' during loading:
> 
> 1. allocate the strlen() of each word
> 2. allocate a fixed length (len of longest word = 32)
> 
> I figured getting strlen(word) each time would be slower than allocating 
> a fixed amt of memory, but that wasn't the case.
> 
> Strategy 2 is significantly slower, and uses nearly 3x the memory.
> 
> Also, does anyone have any 'tricks' to make such a file load routine 
> faster/more efficient?  Thanks

How fast do you want it?

You program loaded 2.3 million words (5 combined copies of your test 
file) in about 1.25 seconds (on my slow PC with hard drive, but using 
file caching).

A faster version I created did it in about 0.2 seconds (so perhaps 
50msec for one copy).

That uses this method:

(1) Get the file size (using seek etc)

(2) Allocate a single memory block and load entire file in one go

(3) Do a first pass counting words (assumes one per line), by looking 
for \n characters and setting each to nul

(4) Use that figure to allocate a linear array of char* objects in one 
memory block

(5) Do a second pass which sets each char* to the start of the word, 
then steps a pointer to just past the next nul for the next word.

You shouldn't be bothering with trailing spaces and such here; do that 
once, and write out a new cleaned-up list. Then apps will read that list 
with no further processing.

(I didn't have time to do a C version; the following outlines my method 
using another systems language:)

------------------------------------------
proc start=
     ichar s,t
     int nwords:=0, c
     ref[]ichar words

     s:=readfile("/texts/words5.")
     t:=s

     while c:=t^ do
         if c=10 then
             ++nwords
             t^:=0
         fi
         ++t
     od

     words:=malloc((nwords+2)*ichar.bytes)

     t:=s
     for i in 1..nwords do
         words[i]:=t
         repeat
         until (++t)^=0
         ++t
     od

     for i in 1..nwords do
         if i in 1..10 or i in nwords-9..nwords then
             println i,words[i]
         fi
     od
end

[toc] | [prev] | [next] | [standalone]

#161970

On 7/19/21 2:01 PM, Bart wrote:
> On 19/07/2021 17:50, dfs wrote:
>> Loaded a list of words into an array.
>>
>> The 370103 words came from https://github.com/dwyl/english-words
>> file = words_alpha.txt
>>
>> Tested a couple memory allocation 'strategies' during loading:
>>
>> 1. allocate the strlen() of each word
>> 2. allocate a fixed length (len of longest word = 32)
>>
>> I figured getting strlen(word) each time would be slower than 
>> allocating a fixed amt of memory, but that wasn't the case.
>>
>> Strategy 2 is significantly slower, and uses nearly 3x the memory.

Any thoughts on this?


>> Also, does anyone have any 'tricks' to make such a file load routine 
>> faster/more efficient?  Thanks
> 
> How fast do you want it?

As fast as possible!


> You program loaded 2.3 million words (5 combined copies of your test 
> file) in about 1.25 seconds (on my slow PC with hard drive, but using 
> file caching).

0.1 seconds here for (1 * 370103 =  370103) on my old system
0.5 seconds for (6 * 370103 = 2220618)


> A faster version I created did it in about 0.2 seconds (so perhaps 
> 50msec for one copy).
> 
> That uses this method:
> 
> (1) Get the file size (using seek etc)
> 
> (2) Allocate a single memory block and load entire file in one go
> 
> (3) Do a first pass counting words (assumes one per line), by looking 
> for \n characters and setting each to nul
> 
> (4) Use that figure to allocate a linear array of char* objects in one 
> memory block
> 
> (5) Do a second pass which sets each char* to the start of the word, 
> then steps a pointer to just past the next nul for the next word.
> 
> You shouldn't be bothering with trailing spaces and such here; do that 
> once, and write out a new cleaned-up list. Then apps will read that list 
> with no further processing.

Thanks for that breakdown.  I'll try to replicate it.


> (I didn't have time to do a C version; the following outlines my method 
> using another systems language:)
> 
> ------------------------------------------
> proc start=
>      ichar s,t
>      int nwords:=0, c
>      ref[]ichar words
> 
>      s:=readfile("/texts/words5.")
>      t:=s
> 
>      while c:=t^ do
>          if c=10 then
>              ++nwords
>              t^:=0
>          fi
>          ++t
>      od
> 
>      words:=malloc((nwords+2)*ichar.bytes)
> 
>      t:=s
>      for i in 1..nwords do
>          words[i]:=t
>          repeat
>          until (++t)^=0
>          ++t
>      od
> 
>      for i in 1..nwords do
>          if i in 1..10 or i in nwords-9..nwords then
>              println i,words[i]
>          fi
>      od
> end

Amazing you wrote your own language.  Did you name it?

[toc] | [prev] | [next] | [standalone]

#161971

On 19/07/2021 19:29, dfs wrote:
> On 7/19/21 2:01 PM, Bart wrote:
>> On 19/07/2021 17:50, dfs wrote:
>>> Loaded a list of words into an array.
>>>
>>> The 370103 words came from https://github.com/dwyl/english-words
>>> file = words_alpha.txt
>>>
>>> Tested a couple memory allocation 'strategies' during loading:
>>>
>>> 1. allocate the strlen() of each word
>>> 2. allocate a fixed length (len of longest word = 32)
>>>
>>> I figured getting strlen(word) each time would be slower than 
>>> allocating a fixed amt of memory, but that wasn't the case.
>>>
>>> Strategy 2 is significantly slower, and uses nearly 3x the memory.
> 
> Any thoughts on this?

Well, I must have loaded a different file from yours (words.zip), with 
466,000 words.

The size of that file on disk (and in memory using my method) is 4.8MB, 
so approx 10 bytes per word on average.

Allocating 32 bytes per word will use 3 times as much memory as you say 
(some 14MB)

The speed of it depends the access patterns, but clearly spreading it 
over an extra 9MB means 2/3 of the data loaded into cache mempry is useless.

Note that my method will use a total of 18 bytes per word on a 64-bit 
machine, with a 64-bit pointer per word. I haven't done any random 
access tests; I've concentrated on loading only.

Given that, there might be a way of using a fixed 16 bytes per word, not 
32, but you'd need some way of dealing with words longer than 15 
characters (nul is still needed). Whether that is going to be any 
faster, is hard to predict.

Maybe changing the order (from alphabetical) might help. It really 
depends on what you intend doing. What is needed are some benchmarks for 
an actual application that shows a problem.

There are all sorts of clever ways to arrange strings in memory, but 
some get very complicated.

> 
> 
>>> Also, does anyone have any 'tricks' to make such a file load routine 
>>> faster/more efficient?  Thanks
>>
>> How fast do you want it?
> 
> As fast as possible!

But is this loading the file (which doesn't appeart to be a problem on 
your machine), or doing something else with it?

> Amazing you wrote your own language.  Did you name it?

I usually call it 'M'.

[toc] | [prev] | [next] | [standalone]

#161977

On 7/19/21 2:49 PM, Bart wrote:
> On 19/07/2021 19:29, dfs wrote:
>> On 7/19/21 2:01 PM, Bart wrote:
>>> On 19/07/2021 17:50, dfs wrote:
>>>> Loaded a list of words into an array.
>>>>
>>>> The 370103 words came from https://github.com/dwyl/english-words
>>>> file = words_alpha.txt
>>>>
>>>> Tested a couple memory allocation 'strategies' during loading:
>>>>
>>>> 1. allocate the strlen() of each word
>>>> 2. allocate a fixed length (len of longest word = 32)
>>>>
>>>> I figured getting strlen(word) each time would be slower than 
>>>> allocating a fixed amt of memory, but that wasn't the case.
>>>>
>>>> Strategy 2 is significantly slower, and uses nearly 3x the memory.
>>
>> Any thoughts on this?
> 
> Well, I must have loaded a different file from yours (words.zip), with 
> 466,000 words.

https://github.com/dwyl/english-words
file = words_alpha.txt
It's sorted


> The size of that file on disk (and in memory using my method) is 4.8MB, 
> so approx 10 bytes per word on average.
> 
> Allocating 32 bytes per word will use 3 times as much memory as you say 
> (some 14MB)
> 
> The speed of it depends the access patterns, but clearly spreading it 
> over an extra 9MB means 2/3 of the data loaded into cache mempry is 
> useless.
> 
> Note that my method will use a total of 18 bytes per word on a 64-bit 
> machine, with a 64-bit pointer per word. I haven't done any random 
> access tests; I've concentrated on loading only.
> 
> Given that, there might be a way of using a fixed 16 bytes per word, not 
> 32, but you'd need some way of dealing with words longer than 15 
> characters (nul is still needed). Whether that is going to be any 
> faster, is hard to predict.
> 
> Maybe changing the order (from alphabetical) might help. It really 
> depends on what you intend doing. What is needed are some benchmarks for 
> an actual application that shows a problem.

There's no problem, per se.  Just trying to learn good techniques.


> There are all sorts of clever ways to arrange strings in memory, but 
> some get very complicated.

Thanks.  'Very complicated' sounds like trouble.

The speed I get is actually fine - who can argue with 0.003s to find 25K 
matching words in a list of 370K words?

I'll try your suggestions.



>>>> Also, does anyone have any 'tricks' to make such a file load routine 
>>>> faster/more efficient?  Thanks
>>>
>>> How fast do you want it?
>>
>> As fast as possible!
> 
> But is this loading the file (which doesn't appeart to be a problem on 
> your machine), or doing something else with it?
> 
>> Amazing you wrote your own language.  Did you name it?
> 
> I usually call it 'M'.

For Mistress?

[toc] | [prev] | [next] | [standalone]

#161981

On 19/07/2021 23:01, dfs wrote:
> On 7/19/21 2:49 PM, Bart wrote:

> 
>> There are all sorts of clever ways to arrange strings in memory, but 
>> some get very complicated.
> 
> Thanks.  'Very complicated' sounds like trouble.

I choose the simplest methods too.

In my script language, I read such a file like this:

  words := readtextfile(file)

This function reads it line by line into a list of string objects 
(somewhere in there is a loop with fgets in it). It's a bit slower, but 
it reads your test file in under 0.3 seconds.

(I use it in a program that helps me cheat at crosswords.)



>> I usually call it 'M'.
> 
> For Mistress?
> 

I wish...

[toc] | [prev] | [next] | [standalone]

#161974

dfs <nospam@dfs.com> writes:
>On 7/19/21 2:01 PM, Bart wrote:
>> On 19/07/2021 17:50, dfs wrote:
>>> Loaded a list of words into an array.
>>>
>>> The 370103 words came from https://github.com/dwyl/english-words
>>> file = words_alpha.txt
>>>
>>> Tested a couple memory allocation 'strategies' during loading:
>>>
>>> 1. allocate the strlen() of each word
>>> 2. allocate a fixed length (len of longest word = 32)
>>>
>>> I figured getting strlen(word) each time would be slower than 
>>> allocating a fixed amt of memory, but that wasn't the case.
>>>
>>> Strategy 2 is significantly slower, and uses nearly 3x the memory.
>
>Any thoughts on this?
>
>
>>> Also, does anyone have any 'tricks' to make such a file load routine 
>>> faster/more efficient?  Thanks


Personally, I'd mmap it and make a single scanning pass over the entire
set of words and build an array of offsets from the start of the
map for each word;  the only allocations would be required to
extend the array (e.g. a vector of 32-bit offset values
or const char * pointers).  If the
words are delimited by LF, CR or CRLF, just write a nul byte
over the delimiter.

Voila, an array of words.

[toc] | [prev] | [next] | [standalone]

#161984

On 2021-07-19, Scott Lurndal <scott@slp53.sl.home> wrote:
> dfs <nospam@dfs.com> writes:
>>On 7/19/21 2:01 PM, Bart wrote:
>>> On 19/07/2021 17:50, dfs wrote:
>>>> Loaded a list of words into an array.
>>>>
>>>> The 370103 words came from https://github.com/dwyl/english-words
>>>> file = words_alpha.txt
>>>>
>>>> Tested a couple memory allocation 'strategies' during loading:
>>>>
>>>> 1. allocate the strlen() of each word
>>>> 2. allocate a fixed length (len of longest word = 32)
>>>>
>>>> I figured getting strlen(word) each time would be slower than 
>>>> allocating a fixed amt of memory, but that wasn't the case.
>>>>
>>>> Strategy 2 is significantly slower, and uses nearly 3x the memory.
>>
>>Any thoughts on this?
>>
>>
>>>> Also, does anyone have any 'tricks' to make such a file load routine 
>>>> faster/more efficient?  Thanks
>
>
> Personally, I'd mmap it and make a single scanning pass over the entire
> set of words and build an array of offsets from the start of the
> map for each word;  the only allocations would be required to
> extend the array (e.g. a vector of 32-bit offset values
> or const char * pointers).  If the
> words are delimited by LF, CR or CRLF, just write a nul byte
> over the delimiter.
>
> Voila, an array of words.
>
+1
I would do that too.


-- 
bmaxa now listens Vanguard by yelworC from Collection 88-94

[toc] | [prev] | [next] | [standalone]

#161985

On 19/07/2021 19:29, dfs wrote:
>
> 0.1 seconds here for (1 * 370103 =  370103) on my old system
> 0.5 seconds for (6 * 370103 = 2220618)
>

How are you measuring the timing? Can you check this program by running:

"prog words_alpha.txt"  This is providing the text file name at the 
command prompt to load it.

I have commented out the printf() function in the main() because the 
file is very big to print on the screen.


<==================================================================================>

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

const int STEPSIZE = 100;

char **loadfile(char *fileName, int *len);

int main(int argc, char *argv[])
{
     if (argc == 1)
     {
         perror("Error: ");
         exit(1);
     }

     int length = 0;
     char **words = loadfile(argv[1], &length);

     if (!words)
     {
         perror("Error: ");
         exit(1);
     }

     for (int i = 0; words[i] != NULL; i++)
     {
         // printf("%s\n", words[i]);
     }

     printf("Total Lines are: %d", length);
     return EXIT_SUCCESS;
}

char **loadfile(char *fileName, int *len)
{
     FILE *f = fopen(fileName, "r");

     if (!f)
     {
         perror("Error: ");
         return NULL;
     }

     int arrlen = STEPSIZE;
     // char **lines = NULL;
     char **lines = (char **)malloc(arrlen * sizeof(char *));

     char buf[1000];
     int i = 0;
     while (fgets(buf, 1000, f))
     {
         if (i == arrlen)
         {
             arrlen += STEPSIZE;
             char **newlines = realloc(lines, arrlen * sizeof(char *));

             if (!newlines)
             {
                 perror("Error: ");
                 exit(1);
             }

             lines = newlines;
         }

         buf[strlen(buf) - 1] = '\0';

         int slen = strlen(buf);
         char *str = (char *)malloc((slen + 1) * sizeof(char));
         strcpy(str, buf);
         lines[i] = str;
         i++;
     }
     *len = i;
     fclose(f);
     return lines;
}

<==================================================================================>

[toc] | [prev] | [next] | [standalone]

#161986

On 7/19/2021 7:30 PM, Real Troll wrote:
> On 19/07/2021 19:29, dfs wrote:
>>
>> 0.1 seconds here for (1 * 370103 =  370103) on my old system
>> 0.5 seconds for (6 * 370103 = 2220618)
>>
> 
> How are you measuring the timing? 


When I first posted the code I was running Linux (gcc) and it had no 
timing code so I used the standard:
$ time ./loadwords wordfile

I later added CLOCK_MONOTONIC_RAW timing to the source code.  You 
probably know already that on Windows you can use the 
QueryPerformanceCounter() in the code.

I'm back on Windows now (tcc compiler), and can use an outside timer 
called ptime.

$ tcc -Wall realtroll.c -o realtroll.exe
$ ptime realtroll words_alpha.txt
Total Lines are: 370103
Execution time: 0.529 s



> Can you check this program by running:
> 
> "prog words_alpha.txt"  This is providing the text file name at the
> command prompt to load it.
> 
> I have commented out the printf() function in the main() because the
> file is very big to print on the screen.
> 
> 
> <==================================================================================>
> 
> #include <stdio.h>
> #include <stdlib.h>
> #include <string.h>
> 
> const int STEPSIZE = 100;
> 
> char **loadfile(char *fileName, int *len);
> 
> int main(int argc, char *argv[])
> {
>       if (argc == 1)
>       {
>           perror("Error: ");
>           exit(1);
>       }
> 
>       int length = 0;
>       char **words = loadfile(argv[1], &length);
> 
>       if (!words)
>       {
>           perror("Error: ");
>           exit(1);
>       }
> 
>       for (int i = 0; words[i] != NULL; i++)
>       {
>           // printf("%s\n", words[i]);
>       }
> 
>       printf("Total Lines are: %d", length);
>       return EXIT_SUCCESS;
> }
> 
> char **loadfile(char *fileName, int *len)
> {
>       FILE *f = fopen(fileName, "r");
> 
>       if (!f)
>       {
>           perror("Error: ");
>           return NULL;
>       }
> 
>       int arrlen = STEPSIZE;
>       // char **lines = NULL;
>       char **lines = (char **)malloc(arrlen * sizeof(char *));
> 
>       char buf[1000];
>       int i = 0;
>       while (fgets(buf, 1000, f))
>       {
>           if (i == arrlen)
>           {
>               arrlen += STEPSIZE;
>               char **newlines = realloc(lines, arrlen * sizeof(char *));
> 
>               if (!newlines)
>               {
>                   perror("Error: ");
>                   exit(1);
>               }
> 
>               lines = newlines;
>           }
> 
>           buf[strlen(buf) - 1] = '\0';
> 
>           int slen = strlen(buf);
>           char *str = (char *)malloc((slen + 1) * sizeof(char));
>           strcpy(str, buf);
>           lines[i] = str;
>           i++;
>       }
>       *len = i;
>       fclose(f);
>       return lines;
> }
> 
> <==================================================================================>

[toc] | [prev] | [next] | [standalone]

#161998

On 20/07/2021 01:40, DFS wrote:
> On 7/19/2021 7:30 PM, Real Troll wrote:
>> On 19/07/2021 19:29, dfs wrote:
>>>
>>> 0.1 seconds here for (1 * 370103 =  370103) on my old system
>>> 0.5 seconds for (6 * 370103 = 2220618)
>>>
>>
>> How are you measuring the timing? 
>
>
> When I first posted the code I was running Linux (gcc) and it had no 
> timing code so I used the standard:
> $ time ./loadwords wordfile
>
> I later added CLOCK_MONOTONIC_RAW timing to the source code.  You 
> probably know already that on Windows you can use the 
> QueryPerformanceCounter() in the code.
>
> I'm back on Windows now (tcc compiler), and can use an outside timer 
> called ptime.
>
> $ tcc -Wall realtroll.c -o realtroll.exe
> $ ptime realtroll words_alpha.txt
> Total Lines are: 370103
> Execution time: 0.529 s
>
>
>
>
I have always used something like this:

clock_t t;
t = clock();
char **words = loadfile(argv[1], &length);
t = clock() - t;

Then use a printf like so:

double time_taken = ((double)t) / CLOCKS_PER_SEC;
printf("loadfile took %f seconds to execute \n", time_taken);

It is quite rudimentary but works most of the time.

In my code example I tweaked some numbers and the time taken was reduced 
dramatically but not as low as your figures.

The numbers I changed were:

const int STEPSIZE = 100000;
char buf[1000000];

Your timings are still very fast.

[toc] | [prev] | [next] | [standalone]

#162046

On 2021-07-19, dfs <nospam@dfs.com> wrote:
> On 7/19/21 2:01 PM, Bart wrote:
>> On 19/07/2021 17:50, dfs wrote:
>>> Loaded a list of words into an array.
>>>
>>> The 370103 words came from https://github.com/dwyl/english-words
>>> file = words_alpha.txt
>>>
>>> Tested a couple memory allocation 'strategies' during loading:
>>>
>>> 1. allocate the strlen() of each word
>>> 2. allocate a fixed length (len of longest word = 32)
>>>
>>> I figured getting strlen(word) each time would be slower than 
>>> allocating a fixed amt of memory, but that wasn't the case.
>>>
>>> Strategy 2 is significantly slower, and uses nearly 3x the memory.
>
> Any thoughts on this?

It must be that malloc is decently optimized for very small object sizes?

[toc] | [prev] | [next] | [standalone]

#161972

On 19/07/2021 18:50, dfs wrote:
> Loaded a list of words into an array.
> 
> The 370103 words came from https://github.com/dwyl/english-words
> file = words_alpha.txt
> 
> Tested a couple memory allocation 'strategies' during loading:
> 
> 1. allocate the strlen() of each word
> 2. allocate a fixed length (len of longest word = 32)
> 
> I figured getting strlen(word) each time would be slower than allocating
> a fixed amt of memory, but that wasn't the case.
> 
> Strategy 2 is significantly slower, and uses nearly 3x the memory.
> 
> Also, does anyone have any 'tricks' to make such a file load routine
> faster/more efficient?  Thanks
> 

#define max_word_count 500000
#define max_word_len 32


// Load your word file with:
char * word_file = malloc(max_word_count * max_word_len);
fgets(word_file, max_word_count * max_word_len, fwords);

// Put your words here:
static char words[max_word_count][max_word_len];


Adjust all that to suit - but the point is, don't mess around with
thousands of mallocs and char pointers.  Your PC has 16 MB to spare.  If
you want speed, use static arrays (or a single big malloc's), not vast
numbers of small mallocs and extra pointers.  Similarly, use a single
large read, not lots of tiny reads.

[toc] | [prev] | [next] | [standalone]

#161978

On 7/19/21 3:35 PM, David Brown wrote:
> On 19/07/2021 18:50, dfs wrote:
>> Loaded a list of words into an array.
>>
>> The 370103 words came from https://github.com/dwyl/english-words
>> file = words_alpha.txt
>>
>> Tested a couple memory allocation 'strategies' during loading:
>>
>> 1. allocate the strlen() of each word
>> 2. allocate a fixed length (len of longest word = 32)
>>
>> I figured getting strlen(word) each time would be slower than allocating
>> a fixed amt of memory, but that wasn't the case.
>>
>> Strategy 2 is significantly slower, and uses nearly 3x the memory.
>>
>> Also, does anyone have any 'tricks' to make such a file load routine
>> faster/more efficient?  Thanks
>>
> 
> #define max_word_count 500000
> #define max_word_len 32
> 
> 
> // Load your word file with:
> char * word_file = malloc(max_word_count * max_word_len);
> fgets(word_file, max_word_count * max_word_len, fwords);
> 
> // Put your words here:
> static char words[max_word_count][max_word_len];
> 
> 
> Adjust all that to suit - but the point is, don't mess around with
> thousands of mallocs and char pointers.  

I did that so I could load smaller and larger (and really large) files.


> Your PC has 16 MB to spare.  If
> you want speed, use static arrays (or a single big malloc's), not vast
> numbers of small mallocs and extra pointers.  Similarly, use a single
> large read, not lots of tiny reads.

Good points.  Between Bart's and your techniques I have some good things 
to try.

It's just the beginning of a simple linear pattern-match routine: how 
many words in the dictionary begin with 'cat'.. that kind of thing.

Thanks for your help.

[toc] | [prev] | [next] | [standalone]

#161975

On 2021-07-19, dfs <nospam@dfs.com> wrote:
> 		//different memory allocations
> 		if(memoption==1)
> 		{memlen=strlen(word);}

/* allocate one extra for the terminating null character */
                 memlen = strlen(word) + 1;

> 		else
> 		{memlen=maxlen;}
> 		
> 		words[i] = malloc(sizeof(char*) * memlen);

/* words[i] contains memlen chars, not memlen pointers to char */
  		words[i] = malloc(sizeof(char) * memlen);
       /* or */ words[i] = malloc(memlen); /* sizeof(char) == 1 by definition */
       /* or */ words[i] = malloc(memlen * sizeof *words[i]); /* clc idiom */

> 		memtotal += memlen;
> 		
> 		strcpy(words[i],word);
> 		
> 		//printf("%d. '%s' ",i,words[i]);
> 		i++;
> 	}
> 		
> 	fclose(fwords);
> 	printf("\nloaded %d words\n",i-1);

/* the number of words is i (numbered from 0 to i-1) */
  	printf("\nloaded %d words\n",i);

> 	printf("\nFirst and Last words = '%s', '%s'\n",words[0],words[i-1]);

[toc] | [prev] | [next] | [standalone]

#161979

On 7/19/21 5:11 PM, Ike Naar wrote:
> On 2021-07-19, dfs <nospam@dfs.com> wrote:
>> 		//different memory allocations
>> 		if(memoption==1)
>> 		{memlen=strlen(word);}
> 
> /* allocate one extra for the terminating null character */
>                   memlen = strlen(word) + 1;


I did it right.  Look a few lines up (you snipped it)

strcpy(word,rtrim(wordin));

So 'word' already has the nul.



>> 		else
>> 		{memlen=maxlen;}
>> 		
>> 		words[i] = malloc(sizeof(char*) * memlen);

This works.

> /* words[i] contains memlen chars, not memlen pointers to char */
>    		words[i] = malloc(sizeof(char) * memlen);
>         /* or */ words[i] = malloc(memlen); /* sizeof(char) == 1 by definition */
>         /* or */ words[i] = malloc(memlen * sizeof *words[i]); /* clc idiom */


All 3 of those options compile but when run:

lettermatch: malloc.c:2539: sysmalloc: Assertion `(old_top == 
initial_top (av) && old_size == 0) || ((unsigned long) (old_size) >= 
MINSIZE && prev_inuse (old_top) && ((unsigned long) old_end & (pagesize 
- 1)) == 0)' failed.
Aborted (core dumped)




>> 		memtotal += memlen;
>> 		
>> 		strcpy(words[i],word);
>> 		
>> 		//printf("%d. '%s' ",i,words[i]);
>> 		i++;
>> 	}
>> 		
>> 	fclose(fwords);
>> 	printf("\nloaded %d words\n",i-1);
> 
> /* the number of words is i (numbered from 0 to i-1) */
>    	printf("\nloaded %d words\n",i);
> 
>> 	printf("\nFirst and Last words = '%s', '%s'\n",words[0],words[i-1]);


Of course (i starts at 0), but gremlins overcount by 1 so I compensated.

The file has 370103 words in it, but the fgets() block results in 370104.

You can run my code against words_alpha.txt from
https://github.com/dwyl/english-words

And see if it counts correctly.


Thanks for looking at it.

[toc] | [prev] | [next] | [standalone]

#161987

On 2021-07-19, dfs <nospam@dfs.com> wrote:
> On 7/19/21 5:11 PM, Ike Naar wrote:
>> On 2021-07-19, dfs <nospam@dfs.com> wrote:
>>> 		//different memory allocations
>>> 		if(memoption==1)
>>> 		{memlen=strlen(word);}
>> 
>> /* allocate one extra for the terminating null character */
>>                   memlen = strlen(word) + 1;
>
>
> I did it right.  Look a few lines up (you snipped it)
>
> strcpy(word,rtrim(wordin));
>
> So 'word' already has the nul.

Yes, 'word' has the null. And later on, 'word' is strcpy-ed into
words[i], so you want words[i] to have room for the copy
of 'word', including the terminating null character.

>
>
>
>>> 		else
>>> 		{memlen=maxlen;}
>>> 		
>>> 		words[i] = malloc(sizeof(char*) * memlen);
>
> This works.

It works by luck, not by design.

Suppose 'word' contains the 6-character text "potato".
To store this in words[i], 7 bytes are needed (6 for the 
text plus 1 for the terminating null character).

Now suppose sizeof (char*) equals 8 (a common value for a 64-bit system).
Using malloc(sizeof(char*) * memlen) with memlen=6, 8*6 = 48 bytes are allocated
which is more than enough to store the 7 bytes.

But it would be more memory-efficient to allocate 1*7 = 7 bytes.
Hence the malloc(sizeof (char) * memlen) with memlen=7.

[toc] | [prev] | [next] | [standalone]

#161980

On 7/19/21 3:46 PM, Stefan Ram wrote:
> dfs <nospam@dfs.com> writes:
>> Also, does anyone have any 'tricks' to make such a file load routine
>> faster/more efficient?  Thanks
> 
>    A lot depends on what you then want to do with those words.
> 
>    If they are not to be modified, but just to be read later,
>    you can read the whole file into one region of memory
>    and then write a NUL character after each word.

They're just to be read and pattern-matched against.


>    If you need to do some per-word processing while reading,
>    you can still allocate one large region of memory and
>    append each word to it.
> 
>> 	char **words = malloc(sizeof(char*) * lines);
> 
>    I assume that you have your reasons for not checking
>    the result of malloc here.


Program is for me only.

I just tested:
lines = 2000000000;
char **words = malloc(sizeof(char*) * lines);
if(words == NULL)
{
   printf("malloc failed\n");
   exit(0);
}

and it failed and exited.



Thanks

[toc] | [prev] | [next] | [standalone]

#161982

On 19/07/2021 23:21, dfs wrote:
> On 7/19/21 3:46 PM, Stefan Ram wrote:
>> dfs <nospam@dfs.com> writes:
>>> Also, does anyone have any 'tricks' to make such a file load routine
>>> faster/more efficient?  Thanks
>>
>>    A lot depends on what you then want to do with those words.
>>
>>    If they are not to be modified, but just to be read later,
>>    you can read the whole file into one region of memory
>>    and then write a NUL character after each word.
> 
> They're just to be read and pattern-matched against.
> 
> 
>>    If you need to do some per-word processing while reading,
>>    you can still allocate one large region of memory and
>>    append each word to it.
>>
>>>     char **words = malloc(sizeof(char*) * lines);
>>
>>    I assume that you have your reasons for not checking
>>    the result of malloc here.
> 
> 
> Program is for me only.
> 
> I just tested:
> lines = 2000000000;
> char **words = malloc(sizeof(char*) * lines);
> if(words == NULL)
> {
>    printf("malloc failed\n");
>    exit(0);
> }
> 
> and it failed and exited.

Is this a 32-bit system? Or a 32-bit compiler on a 64-bit system?

If so, the largest allocation size might be 2GB, and your request was 
for 8GB.

On a 64-bit system, you might be less lucky, and malloc won't fail even 
if the allocation exceeds physical memory. It'll just get very slow.

Then there's little point in checking the malloc result.

[toc] | [prev] | [next] | [standalone]

#161983

On 7/19/21 6:29 PM, Bart wrote:
> On 19/07/2021 23:21, dfs wrote:
>> On 7/19/21 3:46 PM, Stefan Ram wrote:
>>> dfs <nospam@dfs.com> writes:
>>>> Also, does anyone have any 'tricks' to make such a file load routine
>>>> faster/more efficient?  Thanks
>>>
>>>    A lot depends on what you then want to do with those words.
>>>
>>>    If they are not to be modified, but just to be read later,
>>>    you can read the whole file into one region of memory
>>>    and then write a NUL character after each word.
>>
>> They're just to be read and pattern-matched against.
>>
>>
>>>    If you need to do some per-word processing while reading,
>>>    you can still allocate one large region of memory and
>>>    append each word to it.
>>>
>>>>     char **words = malloc(sizeof(char*) * lines);
>>>
>>>    I assume that you have your reasons for not checking
>>>    the result of malloc here.
>>
>>
>> Program is for me only.
>>
>> I just tested:
>> lines = 2000000000;
>> char **words = malloc(sizeof(char*) * lines);
>> if(words == NULL)
>> {
>>    printf("malloc failed\n");
>>    exit(0);
>> }
>>
>> and it failed and exited.
> 
> Is this a 32-bit system? Or a 32-bit compiler on a 64-bit system?

64 on 64

$ gcc -v
Using built-in specs.
COLLECT_GCC=gcc
COLLECT_LTO_WRAPPER=/usr/lib64/gcc/x86_64-suse-linux/11/lto-wrapper
OFFLOAD_TARGET_NAMES=nvptx-none:amdgcn-amdhsa
OFFLOAD_TARGET_DEFAULT=1
Target: x86_64-suse-linux
Configured with: ../configure --prefix=/usr --infodir=/usr/share/info 
--mandir=/usr/share/man --libdir=/usr/lib64 --libexecdir=/usr/lib64 
--enable-languages=c,c++,objc,fortran,obj-c++,ada,go,d,jit 
--enable-offload-targets=nvptx-none,amdgcn-amdhsa, --without-cuda-driver 
--enable-host-shared --enable-checking=release --disable-werror 
--with-gxx-include-dir=/usr/include/c++/11 --enable-ssp --disable-libssp 
--disable-libvtv --enable-cet=auto --disable-libcc1 --enable-plugin 
--with-bugurl=https://bugs.opensuse.org/ --with-pkgversion='SUSE Linux' 
--with-slibdir=/lib64 --with-system-zlib 
--enable-libstdcxx-allocator=new --disable-libstdcxx-pch 
--enable-libphobos --enable-version-specific-runtime-libs 
--with-gcc-major-version-only --enable-linker-build-id 
--enable-linux-futex --enable-gnu-indirect-function --program-suffix=-11 
--without-system-libunwind --enable-multilib --with-arch-32=x86-64 
--with-tune=generic --with-build-config=bootstrap-lto-lean 
--enable-link-mutex --build=x86_64-suse-linux --host=x86_64-suse-linux
Thread model: posix
Supported LTO compression algorithms: zlib zstd
gcc version 11.1.1 20210510 [revision 
23855a176609fe8dda6abaf2b21846b4517966eb] (SUSE Linux)


> If so, the largest allocation size might be 2GB, and your request was 
> for 8GB.
> 
> On a 64-bit system, you might be less lucky, and malloc won't fail even 
> if the allocation exceeds physical memory. It'll just get very slow.

I just listen to my fan to know the workload (it goes up and down a lot 
in Linux).  In Windows 8.1 it stayed quiet, but with Win10 it also 
speeds up and down a lot.



> Then there's little point in checking the malloc result.

I've never done it.  My code is small-time for personal use.

[toc] | [prev] | [next] | [standalone]

Page 1 of 2  [1] 2  Next page →

Back to top | Article view | comp.lang.c

csiph-web