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

Groups > comp.lang.c > #161969

Re: Allocate length of word vs fixed length

Show all headers | View raw

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

Back to comp.lang.c | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

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

csiph-web