pre-allocating a buffer is not an option, it should be dynamic On Sunday, May 8, 2022 at 1:24:40 PM UTC-7 Barnim Dzwillo wrote:
> I had a similar use case in the past and got the best performance when > using ReadSlice() instead of scanner.Scan(). > See sample code here: https://go.dev/play/p/EfvadCURcXt > > On Sunday, May 8, 2022 at 7:25:29 AM UTC+2 Amnon wrote: > >> So you raise a couple of questions: >> >> 1) How about handling runes? >> The nice thing about utf8 is you don't have to care. If you are searching >> for the word ascii byte 'test', you can >> simply compare byte by byte - the letter t is represented by 0x74, and >> this byte in the search buffer can >> only represent t - it can never be part of a multi-byte-rune - not in >> utf8. >> >> 2) Can we handle lines of hundreds of MB? >> Not really. The default will limit MaxTokenSize to 64K. >> If you set your own buffer (recommended) then the size of this buffer >> will be your maximum line length. >> Unfortunately you can't really solve this problem without slurping the >> entire file into memory. Because >> the whole file could consist of a single line, with the word "test" at >> the very end - and at this point, you will >> still need access to the beginning of the file in order to output it. >> >> 3) The Mike Haertel message (from 2010) is interesting, as is the >> reference to the paper >> "Fast String Searching", by Andrew Hume and Daniel Sunday, in the >> November 1991 issue of Software Practice & Experience >> All this is a quite old. Computer architecture has changed significantly >> since then, CPUs have got a lot faster and added vector >> instructions which speed up dumb algorithms a lot. The relative cost of >> accessing memory has massively increased, as memory >> speeds have not increased at anything like the rate of CPU speeds (though >> the Apple M1 system on chips family has changed this) >> so memory -> CPU is often the bottleneck, and optimising CPU performance >> through clever algorithms often merely results in >> the CPU being stuck in stall cycles waiting for cache misses to be >> serviced. >> That said, some of the points Mike makes are still valid. One is the >> massive cost of breaking up lines - which slows down performance >> by an order of magnitude, by forcing you to examine every byte. So >> searching for the search-text, and then when you find it, searching >> backwards >> from that point to find the enclosing line, is a big win. >> The other point he makes which is still valid is to consider the cost of >> copying data. >> This will probably be the dominant cost. Running `cat > /dev/null` will >> tell you how long it takes to merely read the data, and this will give >> you a baseline figure. A reasonably carefully written grep clone should >> achieve roughly the same runtime. >> >> As you specified the problem as reading from stdin, using memory mapped >> files, using faster filesystems and fast SSDs will not help you. >> >> And, as always in Go, allocations trump almost everything else. If you >> end up converting each line into a string, forcing allocations and GC work, >> that will knock orders of magnitude off your performance. >> >> Disclaimer: I have not actually written any code or run any benchmarks >> here. But there are some interesting questions which could make an >> interesting paper. To what extent has Hume and Sunday's 1991 paper been >> invalidated by hardware changes? Are smart algorithm's which >> avoid looking at every byte still a win, or do they actually slow down >> performance by adding branch mispredictions, and preventing vectorisation >> optimisations? To what extent does the Apple/Arm system on chip family, >> with their much lower memory latency, change these considerations? >> How much slower will a simple Go clone of grep be than the C version >> which has had decades of optimisation? >> And how much effort would it take to optimise the Go clone to reach the >> performance of the C version? >> If anyone wants to write the code, do the benchmarks, and publish the >> conclusions, then send me a link. It will be an interesting read. >> >> >> On Sunday, 8 May 2022 at 00:55:28 UTC+1 Const V wrote: >> >>> I cannot use fgrep in this environment. >>> >>> Looks like Scan buffer is resizable. >>> >>> https://cs.opensource.google/go/go/+/refs/tags/go1.18.1:src/bufio/scan.go;l=190 >>> // Is the buffer full? If so, resize. >>> if s >>> <https://cs.opensource.google/go/go/+/refs/tags/go1.18.1:src/bufio/scan.go;drc=a131fd1313e0056ad094d234c67648409d081b8c;l=135> >>> .end >>> <https://cs.opensource.google/go/go/+/refs/tags/go1.18.1:src/bufio/scan.go;drc=a131fd1313e0056ad094d234c67648409d081b8c;l=36> >>> >>> == len(s >>> <https://cs.opensource.google/go/go/+/refs/tags/go1.18.1:src/bufio/scan.go;drc=a131fd1313e0056ad094d234c67648409d081b8c;l=135> >>> .buf >>> <https://cs.opensource.google/go/go/+/refs/tags/go1.18.1:src/bufio/scan.go;drc=a131fd1313e0056ad094d234c67648409d081b8c;l=34>) >>> >>> { >>> // Guarantee no overflow in the multiplication below. >>> const maxInt >>> <https://cs.opensource.google/go/go/+/refs/tags/go1.18.1:src/bufio/scan.go;bpv=1;bpt=1;l=193?gsn=maxInt&gs=kythe%3A%2F%2Fgo.googlesource.com%2Fgo%3Flang%3Dgo%3Fpath%3Dbufio%23const%2520%255Bscan.go%2523192%255D.maxInt> >>> >>> = int >>> <https://cs.opensource.google/go/go/+/refs/tags/go1.18.1:src/bufio/scan.go;bpv=1;bpt=1;l=193?gsn=int&gs=kythe%3A%2F%2Fgo.googlesource.com%2Fgo%3Flang%3Dgo%23int%2523builtin> >>> (^uint >>> <https://cs.opensource.google/go/go/+/refs/tags/go1.18.1:src/bufio/scan.go;bpv=1;bpt=1;l=193?gsn=uint&gs=kythe%3A%2F%2Fgo.googlesource.com%2Fgo%3Flang%3Dgo%23uint%2523builtin>(0) >>> >>> >> 1) >>> if len(s >>> <https://cs.opensource.google/go/go/+/refs/tags/go1.18.1:src/bufio/scan.go;drc=a131fd1313e0056ad094d234c67648409d081b8c;l=135> >>> .buf >>> <https://cs.opensource.google/go/go/+/refs/tags/go1.18.1:src/bufio/scan.go;drc=a131fd1313e0056ad094d234c67648409d081b8c;l=34>) >>> >>> >= s >>> <https://cs.opensource.google/go/go/+/refs/tags/go1.18.1:src/bufio/scan.go;drc=a131fd1313e0056ad094d234c67648409d081b8c;l=135> >>> .maxTokenSize >>> <https://cs.opensource.google/go/go/+/refs/tags/go1.18.1:src/bufio/scan.go;drc=a131fd1313e0056ad094d234c67648409d081b8c;l=32> >>> >>> || len(s >>> <https://cs.opensource.google/go/go/+/refs/tags/go1.18.1:src/bufio/scan.go;drc=a131fd1313e0056ad094d234c67648409d081b8c;l=135> >>> .buf >>> <https://cs.opensource.google/go/go/+/refs/tags/go1.18.1:src/bufio/scan.go;drc=a131fd1313e0056ad094d234c67648409d081b8c;l=34>) >>> >>> > maxInt >>> <https://cs.opensource.google/go/go/+/refs/tags/go1.18.1:src/bufio/scan.go;drc=a131fd1313e0056ad094d234c67648409d081b8c;l=192>/2 >>> >>> { >>> s >>> <https://cs.opensource.google/go/go/+/refs/tags/go1.18.1:src/bufio/scan.go;drc=a131fd1313e0056ad094d234c67648409d081b8c;l=135> >>> .setErr >>> <https://cs.opensource.google/go/go/+/refs/tags/go1.18.1:src/bufio/scan.go;drc=a131fd1313e0056ad094d234c67648409d081b8c;l=252> >>> (ErrTooLong >>> <https://cs.opensource.google/go/go/+/refs/tags/go1.18.1:src/bufio/scan.go;drc=a131fd1313e0056ad094d234c67648409d081b8c;l=69>) >>> >>> >>> return false >>> } >>> newSize >>> <https://cs.opensource.google/go/go/+/refs/tags/go1.18.1:src/bufio/scan.go;bpv=1;bpt=1;l=198?gsn=newSize&gs=kythe%3A%2F%2Fgo.googlesource.com%2Fgo%3Flang%3Dgo%3Fpath%3Dbufio%23var%2520%255Bscan.go%2523197%255D.newSize> >>> >>> := len(s >>> <https://cs.opensource.google/go/go/+/refs/tags/go1.18.1:src/bufio/scan.go;drc=a131fd1313e0056ad094d234c67648409d081b8c;l=135> >>> .buf >>> <https://cs.opensource.google/go/go/+/refs/tags/go1.18.1:src/bufio/scan.go;drc=a131fd1313e0056ad094d234c67648409d081b8c;l=34>) >>> >>> * 2 >>> if newSize >>> <https://cs.opensource.google/go/go/+/refs/tags/go1.18.1:src/bufio/scan.go;drc=a131fd1313e0056ad094d234c67648409d081b8c;l=197> >>> >>> == 0 { >>> newSize >>> <https://cs.opensource.google/go/go/+/refs/tags/go1.18.1:src/bufio/scan.go;drc=a131fd1313e0056ad094d234c67648409d081b8c;l=197> >>> >>> = startBufSize >>> <https://cs.opensource.google/go/go/+/refs/tags/go1.18.1:src/bufio/scan.go;drc=a131fd1313e0056ad094d234c67648409d081b8c;l=82> >>> >>> } >>> if newSize >>> <https://cs.opensource.google/go/go/+/refs/tags/go1.18.1:src/bufio/scan.go;drc=a131fd1313e0056ad094d234c67648409d081b8c;l=197> >>> >>> > s >>> <https://cs.opensource.google/go/go/+/refs/tags/go1.18.1:src/bufio/scan.go;drc=a131fd1313e0056ad094d234c67648409d081b8c;l=135> >>> .maxTokenSize >>> <https://cs.opensource.google/go/go/+/refs/tags/go1.18.1:src/bufio/scan.go;drc=a131fd1313e0056ad094d234c67648409d081b8c;l=32> >>> >>> { >>> newSize >>> <https://cs.opensource.google/go/go/+/refs/tags/go1.18.1:src/bufio/scan.go;drc=a131fd1313e0056ad094d234c67648409d081b8c;l=197> >>> >>> = s >>> <https://cs.opensource.google/go/go/+/refs/tags/go1.18.1:src/bufio/scan.go;drc=a131fd1313e0056ad094d234c67648409d081b8c;l=135> >>> .maxTokenSize >>> <https://cs.opensource.google/go/go/+/refs/tags/go1.18.1:src/bufio/scan.go;drc=a131fd1313e0056ad094d234c67648409d081b8c;l=32> >>> >>> } >>> newBuf >>> <https://cs.opensource.google/go/go/+/refs/tags/go1.18.1:src/bufio/scan.go;bpv=1;bpt=1;l=205?gsn=newBuf&gs=kythe%3A%2F%2Fgo.googlesource.com%2Fgo%3Flang%3Dgo%3Fpath%3Dbufio%23var%2520%255Bscan.go%2523204%255D.newBuf> >>> >>> := make([]byte >>> <https://cs.opensource.google/go/go/+/refs/tags/go1.18.1:src/bufio/scan.go;bpv=1;bpt=1;l=205?gsn=byte&gs=kythe%3A%2F%2Fgo.googlesource.com%2Fgo%3Flang%3Dgo%23byte%2523builtin>, >>> >>> newSize >>> <https://cs.opensource.google/go/go/+/refs/tags/go1.18.1:src/bufio/scan.go;drc=a131fd1313e0056ad094d234c67648409d081b8c;l=197>) >>> >>> >>> copy(newBuf >>> <https://cs.opensource.google/go/go/+/refs/tags/go1.18.1:src/bufio/scan.go;drc=a131fd1313e0056ad094d234c67648409d081b8c;l=204>, >>> >>> s >>> <https://cs.opensource.google/go/go/+/refs/tags/go1.18.1:src/bufio/scan.go;drc=a131fd1313e0056ad094d234c67648409d081b8c;l=135> >>> .buf >>> <https://cs.opensource.google/go/go/+/refs/tags/go1.18.1:src/bufio/scan.go;drc=a131fd1313e0056ad094d234c67648409d081b8c;l=34> >>> [s >>> <https://cs.opensource.google/go/go/+/refs/tags/go1.18.1:src/bufio/scan.go;drc=a131fd1313e0056ad094d234c67648409d081b8c;l=135> >>> .start >>> <https://cs.opensource.google/go/go/+/refs/tags/go1.18.1:src/bufio/scan.go;drc=a131fd1313e0056ad094d234c67648409d081b8c;l=35> >>> :s >>> <https://cs.opensource.google/go/go/+/refs/tags/go1.18.1:src/bufio/scan.go;drc=a131fd1313e0056ad094d234c67648409d081b8c;l=135> >>> .end >>> <https://cs.opensource.google/go/go/+/refs/tags/go1.18.1:src/bufio/scan.go;drc=a131fd1313e0056ad094d234c67648409d081b8c;l=36>]) >>> >>> >>> s >>> <https://cs.opensource.google/go/go/+/refs/tags/go1.18.1:src/bufio/scan.go;drc=a131fd1313e0056ad094d234c67648409d081b8c;l=135> >>> .buf >>> <https://cs.opensource.google/go/go/+/refs/tags/go1.18.1:src/bufio/scan.go;drc=a131fd1313e0056ad094d234c67648409d081b8c;l=34> >>> >>> = newBuf >>> <https://cs.opensource.google/go/go/+/refs/tags/go1.18.1:src/bufio/scan.go;drc=a131fd1313e0056ad094d234c67648409d081b8c;l=204> >>> >>> s >>> <https://cs.opensource.google/go/go/+/refs/tags/go1.18.1:src/bufio/scan.go;drc=a131fd1313e0056ad094d234c67648409d081b8c;l=135> >>> .end >>> <https://cs.opensource.google/go/go/+/refs/tags/go1.18.1:src/bufio/scan.go;drc=a131fd1313e0056ad094d234c67648409d081b8c;l=36> >>> >>> -= s >>> <https://cs.opensource.google/go/go/+/refs/tags/go1.18.1:src/bufio/scan.go;drc=a131fd1313e0056ad094d234c67648409d081b8c;l=135> >>> .start >>> <https://cs.opensource.google/go/go/+/refs/tags/go1.18.1:src/bufio/scan.go;drc=a131fd1313e0056ad094d234c67648409d081b8c;l=35> >>> >>> s >>> <https://cs.opensource.google/go/go/+/refs/tags/go1.18.1:src/bufio/scan.go;drc=a131fd1313e0056ad094d234c67648409d081b8c;l=135> >>> .start >>> <https://cs.opensource.google/go/go/+/refs/tags/go1.18.1:src/bufio/scan.go;drc=a131fd1313e0056ad094d234c67648409d081b8c;l=35> >>> >>> = 0 >>> } >>> On Saturday, May 7, 2022 at 4:43:59 PM UTC-7 kortschak wrote: >>> >>>> On Sat, 2022-05-07 at 16:16 -0700, Const V wrote: >>>> > The question is will scanner.Scan handle a line of 100s MB? >>>> >>>> No, at least not by default (https://pkg.go.dev/bufio#Scanner.Buffer). >>>> But that that point you want to start questioning why you're doing what >>>> you're doing. >>>> >>>> Your invocation of grep can be a lot simpler >>>> >>>> ``` >>>> func grep(match string, r io.Reader, stdout, stderr io.Writer) error { >>>> cmd := exec.Command("fgrep", match) >>>> cmd.Stdin = r >>>> cmd.Stdout = stdout >>>> cmd.Stderr = stderr >>>> return cmd.Run() >>>> } >>>> ``` >>>> >>>> You can then do whatever you want with the buffered output and stderr. >>>> You can also make this use a pipe with minor changes if you expect the >>>> output to be long and that stream processing of that would be sensible >>>> (use cmd.Start instead of Run and look into StdoutPipe). >>>> >>>> >>>> -- You received this message because you are subscribed to the Google Groups "golang-nuts" group. To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscr...@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/golang-nuts/23d14932-17a3-4c68-a72d-f3e0b97dcb55n%40googlegroups.com.
