Working and searching in Large files lazarus / 21-General ---------------------------------------------------------------------- andyf97 · 2025-04-09 08:06 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? ---------------------------------------------------------------------- Zvoni · 2025-04-09 09:12 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) ---------------------------------------------------------------------- Packs · 2025-04-10 03:24 If your file is having proper structure then upload on MySQL. In MySQL use fulltext search ---------------------------------------------------------------------- 440bx · 2025-04-10 04:12 Quote from: 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? 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.h tml#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. ---------------------------------------------------------------------- andyf97 · 2025-04-10 07:49 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 ---------------------------------------------------------------------- paule32 · 2025-04-10 13:00 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 ... ---------------------------------------------------------------------- TRon · 2025-04-10 13:07 Quote from: andyf97 on April 10, 2025, 09:49:52 amI 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. But any (buffered) filestream will do as well. ---------------------------------------------------------------------- 440bx · 2025-04-10 13:27 Quote from: andyf97 on April 10, 2025, 09:49:52 amI 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][+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i { --------- ------------------------------------------------------------------ } function MapFile           (            const InFilename    : pchar;              out OutMapAddress : pointer;              out OutModuleSize : DWORD           )         : boolean;  { maps a file                                                             }  var  FileHandle    : THANDLE = INVALID_HANDLE_VALUE;  FileSize      : int64   = 0;  BytesRead     : DWORD   = 0;   MappingHandle : THANDLE = 0; begin  result        := FALSE;  OutMapAddress := nil;  OutModuleSize := 0;   repeat        { scope - not a loop                                        }     { open the file to obtain a handle to it                                  }     FileHandle := CreateFileA(InFilename,                              GENERIC_READ,                            FILE_SHARE_READ,                            nil,                              OPEN_EXISTING,                            FILE_ATTRIBUTE_NORMAL,                              0);     if FileHandle = INVALID_HANDLE_VALUE then    begin      writeln('MapFile: CreateFile failed');      break;    end;     if not GetFileSizeEx(FileHandle, @FileSize) then    begin      writeln('MapFile: GetFileSizeEx failed.');      break;    end;     { the addition of a page (4 * 1024) is to ensure the file is null       }    { terminated and there is extra room which allows testing characters past }    { what would have been the eof.                                         }     { However, note that the extra room is not used, it's there only to       }    { ensure string comparisons can go past the original end of file without  }    { causing an access violation.  Therefore, while the extra room is not    }    { used it is required for the program to operate properly.                }     MappingHandle := CreateFileMappingA(INVALID_HANDLE_VALUE,                                      nil,                    { no security }                                      PAGE_READWRITE,                                      0,                      { size high   }                                      FileSize + (4 * 1024),  { size low    }                                      nil);    if MappingHandle = 0 then  begin      writeln('MapFile: CreateFileMapping failed.');      break;    end;     { commit linear address space to the file mapping                       }     OutMapAddress := MapViewOfFile(MappingHandle,                                   FILE_MAP_ALL_ACCESS,                                   0,                                 0,                                   0);     if OutMapAddress = nil then    begin      writeln('MapFile: MapViewOfFile failed.');      break;       if IsDebuggerPresent() then      begin      DebugBreak();      end;    end;     { read the file into the mapping                                          }     if not ReadFile(FileHandle,                    OutMapAddress,                  FileSize,                   @BytesRead,                    nil)      then    begin      writeln('MapFile: ReadFile failed.');      BytesRead := 0;       if IsDebuggerPresent() then      begin        DebugBreak();      end;       break;    end;     { it would be "profilactic" to set the mapping to read only now that the  }    { file has been read into it.                                           }   until TRUE;   { we no longer need the FileHandle nor the MappingHandle                    }   if FileHandle    <> INVALID_HANDLE_VALUE then CloseHandle(FileHandle);  if MappingHandle <> 0                    then CloseHandle(MappingHandle);   if (OutMapAddress <> nil) and     (BytesRead     <> 0)   then  begin     result        := TRUE;     OutModuleSize := FileSize;  end;end; { --- ---------------------------------------------------------------------- -- } function UnmapFile(InMapAddress : pointer) : boolean;  { as its name indicates, it unmaps a previously mapped file                 } begin  result := UnmapViewOfFile(InMapAddress);end; 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][+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i {  ReadFile                                           ----------------------- }   { WARNING: on Windows 7, the NumberOfBytesRead parameter is NOT optional,   }  {          however, it IS optional in Win 10 (at least in some versions of  }  {          it.                                                            }   function ReadFile             (            { _in_        } InFile                : THANDLE;              { _out_       } OutBuffer             : pointer;              { _in_      } InNumberOfBytesToRead : DWORD;              { _out_       } OutNumberOfBytesRead  : PDWORD;              { _inout_opt_ } InoutoptOverlapped    : POVERLAPPED             )           : BOOL; stdcall; external kernel32;  That way you don't have to do a read every few characters. HTH ---------------------------------------------------------------------- avk · 2025-04-10 15:30 Quote from: 440bx on April 10, 2025, 06:12:40 am... 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][+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i type  TSizeIntArray = array of SizeInt;  function FindBucks(const a: array of Byte): TSizeIntArray;var  r: array of SizeInt = nil;  rLen: SizeInt = 0;  procedure AddMatch(m: SizeInt);  begin    if rLen = Length(r) then SetLength(r, rLen * 2);    r[rLen] := m;    Inc(rLen);  end;var  I, Ofs, Len: SizeInt;  p: PByte;const  INIT_LEN = 256;{$IFDEF FPC_REQUIRES_PROPER_ALIGNMENT}  PATTERN: array[0..5] of Byte = ($24, $24, $24, $24, $24, $24);{$ELSE}  PATTERN = QWord($0000242424242424);{$ENDIF}begin  if Length(a) = 0 then exit(nil);  SetLength(r, INIT_LEN);  p := @a[0];  Len := Length(a);  Ofs := 0;  repeat    I := IndexByte(p[Ofs], Len, $24);    if (I = -1) or (Len - I < SizeOf(PATTERN)) then break;    Inc(Ofs, I+1); Dec(Len, I+1);{$IFDEF FPC_REQUIRES_PROPER_ALIGNMENT}    if CompareByte(p[Ofs-1], PATTERN, SizeOf(PATTERN)) = 0 then begin{$ELSE}    if (PQWord(@p[Ofs-1])^ xor PATTERN) shl 16 = 0 then begin{$ENDIF}    AddMatch(Ofs-1);      Inc(Ofs, 5); Dec(Len, 5);    end;  until False;  SetLength(r, rLen);  Result := r;end;  This should return offsets of all non-overlapping occurrences of $$$$$$. ---------------------------------------------------------------------- 440bx · 2025-04-10 16:01 Quote from: avk on April 10, 2025, 05:30:22 pmFor 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.) ---------------------------------------------------------------------- avk · 2025-04-11 09:57 Quote from: andyf97 on April 10, 2025, 09:49:52 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][+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i procedure ProcessFile(const aFileName: string);var  Data: array of Byte;  DataSize: SizeInt;  ...begin  with TBytesStream.Create do    try      LoadFromFile(aFileName);      Data := Bytes;      DataSize := Size;  finally      Free;    end;  // now all data from your file has been loaded into bytes [0..DataSize-1] of Data array  ...end;  Quote from: 440bx on April 10, 2025, 06:01:46 pm... (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. ---------------------------------------------------------------------- 440bx · 2025-04-11 10:14 Quote from: avk on April 11, 2025, 11:57:10 amOut 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.