#Fastest way to read through a big file byte by byte?

84 messages · Page 1 of 1 (latest)

fathom rapids
#

I'm trying to parse a huge json to find some identifiers in it in the fastest and most memory efficient manner. I'm currently doing:

reader := bufio.NewReader(f)
// Read file byte by byte
for {
    b, err := reader.ReadByte()
    if err != nil {
        if err.Error() == "EOF" {
            break
        }
        return nil, err
    }
    // Do something simple with b that is definitely not a bottleneck,
    // since I get same times even when commenting everything in here out.
}

But it's taking 10 seconds for a 250MB json file, which seems way too slow. I'm assuming I'm doing something wrong right? There has to be a faster way.

idle flower
#

why byte by byte, that's your issue

#

os.ReadFile () + bytes.Index will find in milliseconds yet won't help for json... but strings.Index will

somber harbor
#

on linux you could also mmap an O_DIRECT file, and if you are using NVME and a non checksumming file system and got an updated kernel this might do DMA (this is an insane option in almost all cases, just to point out fastest is almost always what you are not after)

idle flower
#

for 250mb which isn't that big there isn't really a point in trying fancy streaming, though it depends what is the end goal I suppose (vs just loading the whole thing in memory the easiest way possible)

#

I rephrase the question as "best way to read a (somewhat) big file (not) byte by byte" - ie the best way is if it's to search for some bytes, read it in memory and search

fathom rapids
#

I need to find strings of certain signatures. so I'm parsing, and accumulating a slice of bytes until it doesn't match the signature, then I discard it and wait until it starts matching again, and record it if it complies with the whole signature.
anyway, my matching algo works and is fast. it's the byte looping that is slow. and I don't see a reason why looping through streaming bytes should be slower than reading into memory and looping then. but I'm too new in go to know how the internals work and why is it so slow.

#

I don't know how big the json files will get, so I'm definitely not reading them to memory

warm swift
#

sounds to me like a great opportunity to get your hands dirty in some profiling 🙂 you won’t have to take anyone’s word for it

#

it’s a super great skill to have in general

fathom rapids
#

but I don't even know how else to do this. I assumed the reader will read some chunk of file (size optimized for reading speed) and give me bytes it has for processing until it drains, and then read another chunk until EOF.
the only idea I've had is to maybe increase the chunk size, so I swapped it for NewReaderSize(f, 1024 * 1024) (default was I think 4096), but it had no effect on time

idle flower
#

if you still want to only go byte by byte, consider using bufio.NewReaderSize() with a larger buffer than the default 4k

#

damn you said it while I was verifying / copypasting 🙂

warm swift
#

you have the order backwards there, you don’t not profile because you don’t have ideas

fathom rapids
#

yeah, I'm here for someone to tell me what things to throw :)

#

it's 2am here, so I'm going to bed now. I'll try reading to memory and processing from there tomorrow, but that's just to see the difference to satisfy my curiosity, but I can't use that solution
I honestly don't see a reason why streaming should be so much slower than reading to memory

warm swift
#

this is something that a profile can help to answer, without any ambiguity

#

are you spending all your time in syscalls? is something about the loop itself slow? we don’t know, but you can measure it

idle flower
#

^ or maybe you're generating a lot of gc in your loop etc... it won't ever be as fast as simd based Index but it shouldn't be slow either

fathom rapids
#

ok, maybe I was under an illusion of how fast things are. I always thought that when processing files, I/O is always the bottleneck, but I've tried just reading the file into memory, and looping through it to count the dots, and the counting takes double the time the reading took:

start := time.Now()
fileContent := Must(io.ReadAll(f)) // 250MB
fmt.Printf("Reading: %s\n", time.Since(start)) // 0.546s

count := 0
dot := byte('.')
start = time.Now()
for i := 0; i < len(fileContent); i++ {
    if fileContent[i] == dot {
        count++
    }
}
fmt.Printf("Processing: %s\n", time.Since(start)) // 1.299s
fmt.Printf("Count: %d\n", count) // 12680

Is this right?

#

also, when trying to count white space (so comparing against multiple bytes), why is this:

space := byte(' ')
tab := byte('\t')
newline := byte('\n')
for i := 0; i < len(fileContent); i++ {
    if fileContent[i] == space || fileContent[i] == tab || fileContent[i] == newline {
        count++
    }
}

faster than this?

ws := map[byte]bool{
    byte(' '):  true,
    byte('\t'): true,
    byte('\n'): true,
}
for i := 0; i < len(fileContent); i++ {
    if ws[fileContent[i]] {
        count++
    }
}

Isn't it 3 comparisons instead of 1?
Man, I thought I had a good understanding of what is fast and what is slow. My world is crumbling... :)

idle flower
#

try Index* (https://pkg.go.dev/bytes#IndexAny) and have your mind blown away….

also a map access is “o(1)” doesn’t mean faster than local reads

lastly if doing it yourself for bytes you’d use an array marking the elements, and an array[256] avoids bound checks

fathom rapids
#

I don't follow your last sentence. where/how would I use array[256] here?

#

or how would I use bytes.IndexByte here? I need to parse the whole file, not just get the first occurrence of something. I also don't get why would bytes.IndexByte be faster than what I'm doing. Is there a faster way to loop through a slice of bytes than a for..i loop?

idle flower
#

in your code above you are counting occurences not parsing the whole file.

it’s faster because of SIMD

array of 256 booleans for things to filter with if found[b] instead of the ||

fathom rapids
#

oh, you mean this?

var ws [256]bool
ws[byte(' ')] = true
ws[byte('\t')] = true
ws[byte('\n')] = true
for i := 0; i < len(content); i++ {
    if ws[content[i]] {
        count++
    }
}

that is indeed faster. thx for the tip

#

but I still can't accept that this simple bytes processing is 2x slower than reading them from a slow storage

idle flower
#

please try index… (3rd and last attempt)*

#

« slow storage » is OS cached in memory one page at a time, aka 4096x fewer operations than byte by byte

fathom rapids
#

I'm sorry, I see that I'm frustrating you, but I guess I'm still too dumb or ignorant to see how you want me to use the bytes.Index* here :( I'm reading the docs, but all it does is give me the index of the first occurrence? while my string extraction loop (the thing I'm trying to make faster here) needs to read through everything, and the speed testing char counters above also need to know occurrences of all instances

#

specifically what need to do is: I have a json that can have string values (in various nested places) containing indentifiers in a foo.bar.baz format (3 values joined by a dot), and I need to extract the foo.bar parts of that. so I wrote a kind of json parser that is tying to do the minimum amount of work to get these, it identifies :" as start of a string, accumulates it's content and checks if it matches the format when it hits a breaking character

#

here's my current solution: https://snippet.host/ivecpf
I'm sure I'm doing dumb things, so feel free to laugh :)

ivecpf - snippet.host

func FindIdentifiersInJson(f os.File) ([]string, error) {
reader := bufio.NewReaderSize(f, 10241024)
deps := NewSetstring
prevChar := byte(' ')
...

idle flower
# 
ws := " \t\n"
count := 0
start := 0
for {
    i := bytes.IndexAny(content[start:], ws)
    if i < 0 {
        break
    }
    count++
    start += i + 1
}
fathom rapids
#

here's times I see:

3 comparisons against 3 bytes : 1.9s
[256]bool and ws[content[i]]  : 1.14s
bytes.IndexAny                : 5.5s
#

either way, I was at least able to lower the total time of my actual problem from 12s to 3.6s thanks to your tips, so thanks :)

idle flower
#

last one must be off or you’re measuring on a machine without SIMD

#

it should be the fastest

#

I am on my phone or I would run a benchmark but do double check the code (did you confirm all 3 give the same count for your input)

fathom rapids
#

yeah it's a pretty old CPU, i5 6500, but it seems to have SIMD (SSE instructions right?) not sure, this is the first time I'm working on something where I need to know CPU instructions :)
I'll double check the counts

#

yup, all 3 same number

idle flower
#

will check when it’s daylight. for sure if you were trying to count a single byte or a unique sequence Index() would be a lot faster (you could try say counting only spaces to compare) but maybe IndexAny degrades poorly to … 3

#

glad the array version helped at least

fathom rapids
#

now that I know this seems to be hopelessly CPU bottlenecked I'll try to parallelize it. thanks for your time! much appreciated :)

sacred belfry
somber harbor
#

the world is doomed

sacred belfry
idle flower
#

yc while I have you - wouldn't there be a single pass SIMD way to find a small number of bytes?

somber harbor
#

there is, this is a well known problem

somber harbor
#

idk why anything is logical then

sacred belfry
idle flower
#

I was disapointed IndexAny doesn't seem to do anything smart when given 3 bytes, it seems very rune oriented (which is "correct" but not ascii perf oriented)

#

(3 bytes that are 3 runes of 1 byte)

sacred belfry
somber harbor
sacred belfry
#

😂

somber harbor
#

So there are literals you want to find the indexes of ?

#

what are they ?

#

||if they are nearby in the ascii table it helps||

idle flower
#

\t \n and space was the test

sacred belfry
idle flower
#

(already covered the no bound check array way but that's still byte by byte)

#

I'd like a SIMD version that would scan gbytes fast

#

like it does if you look for a single one at a time

somber harbor
#

ok first trick.
Theses are all ascii, so you infact do not need to handle UTF8 to begin with.
Because all the bytes of a multibyte encoded value always have a leading 8th bit set, which something testing for ascii will always ignore

idle flower
#

we were calling bytes.IndexAny (not string... so it should really be some new bytes.IndexAny([]byte) instead of str

idle flower
#

bytes.IndexAnyByte() can that be written / does go assembly let you do simd?

somber harbor
#

I've cut noise about IndexAny's impl, it could be optimized a bit but not much.

For SIMD the loop would be:

  • 1 × SIMD load
  • 3 × SIMD byte comparison
  • 1 or 3 × conditional control flow to break out of the loop if a match is found.

The conditionals will be completely free thx to jump prediction unless your matches are short.
byte wise compare will be something like VPCMPEQB, from memory a Zen5 CPU will be able to execute 2 64 bytes compare per cycle.
Given we need 3 per iteration, we wont bottlenecked by the loads* which can do 1 or 2 per cycle (when we need ⅔ per cycle).

*So it should run at 170GB/s, need less to say, this is fast, much MUCH faster than your RAM can go, so this is memory bottlenecked.

#

You can write that in go asm, but the problem is go asm has architecture instructions that compile to all arches correctly.
Theses are only scallar sadly.
For SIMD you need to write an impl for each arch you want to support.

halcyon citrus
#

they want to count matches so you need to chuck in the mvmsk and popcnt

somber harbor
#

I see, my impl does IndexAny3Bytes

idle flower
#

that's fine/all that's needed to use the loop I put before

# 
ws := []byte(" \t\n")
count := 0
start := 0
for {
    i := bytes.IndexAnyBytes(content[start:], ws)
    if i < 0 {
        break
    }
    count++
    start += i + 1
}

can I haz IndexAnyBytes

somber harbor
#

it would be faster to do what @halcyon citrus said in SIMD so you wouldn't need to exit and renter the SIMD hot loop

#

also counting in simd is just faster than not

idle flower
#

sure but from api point of view it's more surface for a small incremental gain? we don't have a bytes.CountByte(byte) do we

somber harbor
#

I don't think they will add a SIMD version that counts exactly 3 bytes

#

Actually you could do bitset lookups in SIMD it wouldn't be as fast but would be much faster than what it is doing rn

halcyon citrus
idle flower
#

[]byte - I guess a generic version would be histogram of byte value as simd