Lazarus

Programming => General => Topic started by: andyf97 on April 09, 2025, 10:06:42 am

Title: Working and searching in Large files
Post by: andyf97 on April 09, 2025, 10:06:42 am


Hello and good morning.

In Lazarus:

What is the best way ie fastest to search a large file ( 800Meg) for given strings like $$$$$$ and to know position and quantity of string?

For speed, best done with inline assembler?

Should memory mapping be used?






Title: Re: Working and searching in Large files
Post by: Zvoni on April 09, 2025, 11:12:42 am
Probably reading in Chunks (BlockRead?).

NotaBene: Always have 2 consecutive chunks "available"/Combined if the String you're searching for sits exactly on a chunk-border.
e.g. (rudimentary algorithm)
1) read Chunk 1 and 2
2) Concat the chunks to a single Text/String
2) Do your test for occurence of your Search-text (Pos/PosEx/RegEx?). --> In a Loop: your text can occur multiple times. Repeat Loop until nothing found anymore
3) discard preceding chunk and load next chunk
4) Goto 2)

Note2: You have to defend against "already found" (e.g. you have Chunk 1 and 2, and your Text was found in Chunk 2, you discard Chunk 1 and load Chunk 3, your test would find it again in Chunk 2)
No idea about performance.

An alternative might be a TFileStream, but i have no idea how to read in chunks with that (would have to research it)
Title: Re: Working and searching in Large files
Post by: Packs on April 10, 2025, 05:24:09 am
If your file is having proper structure then upload on MySQL.
In MySQL use fulltext search
Title: Re: Working and searching in Large files
Post by: 440bx on April 10, 2025, 06:12:40 am


Hello and good morning.

In Lazarus:

What is the best way ie fastest to search a large file ( 800Meg) for given strings like $$$$$$ and to know position and quantity of string?

For speed, best done with inline assembler?

Should memory mapping be used?



There are two things required to optimize string searches in files, they are: 1. minimize the number of I/Os required to read the file and 2. use an efficient string searching algorithm.

1. presuming you're doing this in Windows, open the file letting the O/S know that you'll do serial reads.  read the entire file into a memory mapping (do a single logical read, let the O/S figure out how to break it into physical reads).  Doing it that way, the O/S will automatically optimize the number of physical I/Os for you.

2. use a reasonably good implementation of the Boyer-Moore algorithm for string searhing.  You can find an implementation at :
https://forum.lazarus.freepascal.org/index.php/topic,44140.msg395066.html#msg395066

Disclaimer, I haven't used that implementation but, the author makes good stuff, I have no reason to believe his implementation of Boyer-Moore is any different.

A reasonably well implemented Boyer-Moore string searching in Pascal will run rings around a sequential search in assembler for large files.  If you want to use assembler then implement Boyer-Moore in assembler and the gain in speed from doing so will be so small that on a multitasking O/S it will probably be undetectable (unless the compiler generates truly atrocious code.)  You'll likely be much better off using avk's code.

HTH.
Title: Re: Working and searching in Large files
Post by: andyf97 on April 10, 2025, 09:49:52 am
Some interesting replies there, thank you.

The data is quite easy to read slowly and consists of :

Data header 46 bytes with the first 6 characters being '$$$$$$' followed by descriptions and size of the data that follows the header, this header also defines the amount of headers in the complete file, the one I look at now I know has 17,000 headers, each with a bunch of data.

47th byte is the start of the data 

Right after the data comes another Data header 46 bytes with the first 6 characters being '$$$$$$' followed by descriptions and size of the data that follows the header, this header does not have a total of the headers but it has a field describing it is header number 1

Repeats until the last data header has no value for data size.


Header: size of the data, amount of headers in the file
Data

Header: size of the data, this header number 1
Data

Header: size of the data, this header number 2
Data
.
.
.
Header: size of the data =0, this header number 17000
Data


So what I am doing now is a bit of a loopy thing using goto, it works ok but is really really slow reading so many bytes at a time from a drive


I open the file then loop thru each character until I find a $, and fall asleep while waiting

start:
blockread single characters until I find a $
goto start

found maybe the first $

blockread the next character to see if is also a $......... if it is not a $ then go back to start..Otherwise continue.
blockread the next character to see if is also a $......... if it is not a $ then go back to start..Otherwise continue.
blockread the next character to see if is also a $......... if it is not a $ then go back to start..Otherwise continue.
blockread the next character to see if is also a $......... if it is not a $ then go back to start..Otherwise continue.
blockread the next character to see if is also a $......... if it is not a $ then go back to start..Otherwise continue.
blockread the next character to see if is also a $......... if it is not a $ then go back to start..Otherwise continue.


If reach here then we have $$$$$$
Store the positions into an Array and then goto start, and so on until end of file.


I would love to be able to read the whole file into a RAM of a kind, where I could then randomly access the data





Title: Re: Working and searching in Large files
Post by: paule32 on April 10, 2025, 03:00:42 pm
My advise would be:

- split the Super File into single Files
- hold a Super File in which you write Positions of Headers.
  - the Headers, you split into several Sections:
    e.g. Header 1 - for all A - Words (fileA.db)
    e.g. Header 2 - for all B - Words (fileB.db)

- then you can Filter your search logic by the trailing alpha numeric Codes for your Word(s).
  e.g. if you search for Anton, you Capture A fron Anton, jump to fileA.db and search Anton in it.

- the fileA.db you can split again, to hold:
  e.g. Abracadabrra (fileAb.db)
  e.g. Anton            (fileAn.db)

- this requieres some steps in programming logic - but you would love it, if you don't want to use a existing Database System like:

- MySQL, or Microsoft-SQL Server

Microsoft-SQL comes with a Free Developer Edition, but I advise you, TO NOT store all Servers on your single Developer PC - on some Reason's it is better to split Database, Web Servers on several Computers.

Blah Blah... and so on, and on so forth ...
Title: Re: Working and searching in Large files
Post by: TRon on April 10, 2025, 03:07:04 pm
I would love to be able to read the whole file into a RAM of a kind, where I could then randomly access the data
TMemorystream (https://www.freepascal.org/docs-html/rtl/classes/tmemorystream.html). But any (buffered) filestream will do as well.
Title: Re: Working and searching in Large files
Post by: 440bx on April 10, 2025, 03:27:26 pm
I would love to be able to read the whole file into a RAM of a kind, where I could then randomly access the data
In Windows, just map the file and read the entire file in a single operation. 

Here is some code that does that:
Code: Pascal  [Select][+][-]
  1. { --------------------------------------------------------------------------- }
  2.  
  3. function MapFile
  4.            (
  5.             const InFilename    : pchar;
  6.               out OutMapAddress : pointer;
  7.               out OutModuleSize : DWORD
  8.            )
  9.          : boolean;
  10.   { maps a file                                                               }
  11.  
  12. var
  13.   FileHandle    : THANDLE = INVALID_HANDLE_VALUE;
  14.   FileSize      : int64   = 0;
  15.   BytesRead     : DWORD   = 0;
  16.  
  17.   MappingHandle : THANDLE = 0;
  18.  
  19. begin
  20.   result        := FALSE;
  21.   OutMapAddress := nil;
  22.   OutModuleSize := 0;
  23.  
  24.   repeat        { scope - not a loop                                          }
  25.  
  26.     { open the file to obtain a handle to it                                  }
  27.  
  28.     FileHandle := CreateFileA(InFilename,
  29.                               GENERIC_READ,
  30.                               FILE_SHARE_READ,
  31.                               nil,
  32.                               OPEN_EXISTING,
  33.                               FILE_ATTRIBUTE_NORMAL,
  34.                               0);
  35.  
  36.     if FileHandle = INVALID_HANDLE_VALUE then
  37.     begin
  38.       writeln('MapFile: CreateFile failed');
  39.       break;
  40.     end;
  41.  
  42.     if not GetFileSizeEx(FileHandle, @FileSize) then
  43.     begin
  44.       writeln('MapFile: GetFileSizeEx failed.');
  45.       break;
  46.     end;
  47.  
  48.     { the addition of a page (4 * 1024) is to ensure the file is null         }
  49.     { terminated and there is extra room which allows testing characters past }
  50.     { what would have been the eof.                                           }
  51.  
  52.     { However, note that the extra room is not used, it's there only to       }
  53.     { ensure string comparisons can go past the original end of file without  }
  54.     { causing an access violation.  Therefore, while the extra room is not    }
  55.     { used it is required for the program to operate properly.                }
  56.  
  57.     MappingHandle := CreateFileMappingA(INVALID_HANDLE_VALUE,
  58.                                         nil,                    { no security }
  59.                                         PAGE_READWRITE,
  60.                                         0,                      { size high   }
  61.                                         FileSize + (4 * 1024),  { size low    }
  62.                                         nil);
  63.     if MappingHandle = 0 then
  64.     begin
  65.       writeln('MapFile: CreateFileMapping failed.');
  66.       break;
  67.     end;
  68.  
  69.     { commit linear address space to the file mapping                         }
  70.  
  71.     OutMapAddress := MapViewOfFile(MappingHandle,
  72.                                    FILE_MAP_ALL_ACCESS,
  73.                                    0,
  74.                                    0,
  75.                                    0);
  76.  
  77.     if OutMapAddress = nil then
  78.     begin
  79.       writeln('MapFile: MapViewOfFile failed.');
  80.       break;
  81.  
  82.       if IsDebuggerPresent() then
  83.       begin
  84.         DebugBreak();
  85.       end;
  86.     end;
  87.  
  88.     { read the file into the mapping                                          }
  89.  
  90.     if not ReadFile(FileHandle,
  91.                     OutMapAddress,
  92.                     FileSize,
  93.                    @BytesRead,
  94.                     nil)        then
  95.     begin
  96.       writeln('MapFile: ReadFile failed.');
  97.       BytesRead := 0;
  98.  
  99.       if IsDebuggerPresent() then
  100.       begin
  101.         DebugBreak();
  102.       end;
  103.  
  104.       break;
  105.     end;
  106.  
  107.     { it would be "profilactic" to set the mapping to read only now that the  }
  108.     { file has been read into it.                                             }
  109.  
  110.   until TRUE;
  111.  
  112.   { we no longer need the FileHandle nor the MappingHandle                    }
  113.  
  114.   if FileHandle    <> INVALID_HANDLE_VALUE then CloseHandle(FileHandle);
  115.   if MappingHandle <> 0                    then CloseHandle(MappingHandle);
  116.  
  117.   if (OutMapAddress <> nil) and
  118.      (BytesRead     <> 0)   then
  119.   begin
  120.      result        := TRUE;
  121.      OutModuleSize := FileSize;
  122.   end;
  123. end;
  124.  
  125. { --------------------------------------------------------------------------- }
  126.  
  127. function UnmapFile(InMapAddress : pointer) : boolean;
  128.   { as its name indicates, it unmaps a previously mapped file                 }
  129.  
  130. begin
  131.   result := UnmapViewOfFile(InMapAddress);
  132. end;
  133.  
Just one possible problem in that code is its use of ReadFile.  I use my own Windows API definitions and I am almost certain that my definition of ReadFile is incompatible with FPC's definition which causes an access violation.  The problem is easy to solve, just declare ReadFile as it is declared by MS:
Code: Pascal  [Select][+][-]
  1. {  ReadFile                                           ----------------------- }
  2.  
  3.   { WARNING: on Windows 7, the NumberOfBytesRead parameter is NOT optional,   }
  4.   {          however, it IS optional in Win 10 (at least in some versions of  }
  5.   {          it.                                                              }
  6.  
  7.   function ReadFile
  8.              (
  9.               { _in_        } InFile                : THANDLE;
  10.               { _out_       } OutBuffer             : pointer;
  11.               { _in_        } InNumberOfBytesToRead : DWORD;
  12.               { _out_       } OutNumberOfBytesRead  : PDWORD;
  13.               { _inout_opt_ } InoutoptOverlapped    : POVERLAPPED
  14.              )
  15.            : BOOL; stdcall; external kernel32;
  16.  

That way you don't have to do a read every few characters.

HTH
Title: Re: Working and searching in Large files
Post by: avk on April 10, 2025, 05:30:22 pm
...
2. use a reasonably good implementation of the Boyer-Moore algorithm for string searhing.
...

For patterns like OP's, a Boyer-Moore search will show rather poor results.
Maybe it makes sense to try something like:
Code: Pascal  [Select][+][-]
  1. type
  2.   TSizeIntArray = array of SizeInt;
  3.  
  4. function FindBucks(const a: array of Byte): TSizeIntArray;
  5. var
  6.   r: array of SizeInt = nil;
  7.   rLen: SizeInt = 0;
  8.   procedure AddMatch(m: SizeInt);
  9.   begin
  10.     if rLen = Length(r) then SetLength(r, rLen * 2);
  11.     r[rLen] := m;
  12.     Inc(rLen);
  13.   end;
  14. var
  15.   I, Ofs, Len: SizeInt;
  16.   p: PByte;
  17. const
  18.   INIT_LEN = 256;
  19. {$IFDEF FPC_REQUIRES_PROPER_ALIGNMENT}
  20.   PATTERN: array[0..5] of Byte = ($24, $24, $24, $24, $24, $24);
  21. {$ELSE}
  22.   PATTERN = QWord($0000242424242424);
  23. {$ENDIF}
  24. begin
  25.   if Length(a) = 0 then exit(nil);
  26.   SetLength(r, INIT_LEN);
  27.   p := @a[0];
  28.   Len := Length(a);
  29.   Ofs := 0;
  30.   repeat
  31.     I := IndexByte(p[Ofs], Len, $24);
  32.     if (I = -1) or (Len - I < SizeOf(PATTERN)) then break;
  33.     Inc(Ofs, I+1); Dec(Len, I+1);
  34. {$IFDEF FPC_REQUIRES_PROPER_ALIGNMENT}
  35.     if CompareByte(p[Ofs-1], PATTERN, SizeOf(PATTERN)) = 0 then begin
  36. {$ELSE}
  37.     if (PQWord(@p[Ofs-1])^ xor PATTERN) shl 16 = 0 then begin
  38. {$ENDIF}
  39.       AddMatch(Ofs-1);
  40.       Inc(Ofs, 5); Dec(Len, 5);
  41.     end;
  42.   until False;
  43.   SetLength(r, rLen);
  44.   Result := r;
  45. end;
  46.  

This should return offsets of all non-overlapping occurrences of $$$$$$.
Title: Re: Working and searching in Large files
Post by: 440bx on April 10, 2025, 06:01:46 pm
For patterns like OP's, a Boyer-Moore search will show rather poor results.
He hadn't shown what he was looking for exactly at the time I made that comment but, still it shouldn't be too bad.  In most cases the algorithm would do only 2 comparisons to eliminate 5 characters.   That's definitely better than the naive method of one comparison per character.

I was thinking about something very similar to what you showed.  Basically scan for a DWORD (binary representation of "$$$$'), if there is a match then check for a WORD ('$$').  Whenever there is no match using the DWORD then if the character that follows the DWORD is not a '$' then the pointer can advance 5 bytes in one shot.  if the character is a '$' then advance just 1 byte.   Repeat till end of buffer.  Effectively that allows a step of 5 characters with only 2 comparisons (I believe the Boyer-Moore algorithm would do as much too but, likely using characters instead of a DWORD and WORD.)


Title: Re: Working and searching in Large files
Post by: avk on April 11, 2025, 11:57:10 am
...
I would love to be able to read the whole file into a RAM of a kind, where I could then randomly access the data

One more way to load a file into memory:
Code: Pascal  [Select][+][-]
  1. procedure ProcessFile(const aFileName: string);
  2. var
  3.   Data: array of Byte;
  4.   DataSize: SizeInt;
  5.   ...
  6. begin
  7.   with TBytesStream.Create do
  8.     try
  9.       LoadFromFile(aFileName);
  10.       Data := Bytes;
  11.       DataSize := Size;
  12.     finally
  13.       Free;
  14.     end;
  15.   // now all data from your file has been loaded into bytes [0..DataSize-1] of Data array
  16.   ...
  17. end;
  18.  

...
(I believe the Boyer-Moore algorithm would do as much too but, likely using characters instead of a DWORD and WORD.)

Out of curiosity, generated an array of 800M random bytes, on which randomly scattered 17000 strings of the form $$$$$$.
Boyer-Moore search - 432 ms, FindBucks() - 82 ms.
Title: Re: Working and searching in Large files
Post by: 440bx on April 11, 2025, 12:14:41 pm
Out of curiosity, generated an array of 800M random bytes, on which randomly scattered 17000 strings of the form $$$$$$.
Boyer-Moore search - 432 ms, FindBucks() - 82 ms.
That's interesting, I would have expected the Boyer-Moore algorithm to do better than that.

Thank you for testing its performance in that case.  I appreciate it.
TinyPortal © 2005-2018