Brendan Hansknecht (Jul 16 2024 at 02:17): Brendan Hansknecht (Jul 16 2024 at 02:17):I think we should add the ability to mmap a file in basic cli. It would be mmaped and passed to roc a seamless slice. This means no copy when loading data into roc. Of course, any attempt to modify the data or otherwise change it would lead to a total copy of the data. During calls to roc_dealloc we can check if the data being freed is in the mmap list. If so, we seamlessly free the mmap.
Thoughts?
Brendan Hansknecht (Jul 16 2024 at 02:18):I think besides the concern of users accidentally causing a copy and manifesting the memory cost, this should be pretty clean to implement.
Brendan Hansknecht (Jul 16 2024 at 02:22):One piece I am not sure the real world cost of:
We need a way to tell when we are freeing the mmap. My base thought is to just do a hashmap(with fast hasher like wyhash) lookup that maps from a pointer to an open mmap. That price would be paid on every dealloc.
If we want to avoid that cost, we could instead pick a static limit to the max number of mmaps and use a list. Then just check if the pointer is in a range that maps to the list element pointers. (So pointer based list contains check). This would just be a greater than and less than op. That said, it requires picking an arbitrary static limit to the number of mmaps.
Richard Feldman (Jul 16 2024 at 03:11):oh I was just thinking we do their allocs in a separate heap
Richard Feldman (Jul 16 2024 at 03:11):(same with file descriptors)
Richard Feldman (Jul 16 2024 at 03:12):then we can at first do "check if pointer is in range" and then if the original range gets exhausted, we can make a second range and start allocating into there (and checking both ranges)
Richard Feldman (Jul 16 2024 at 03:12):then maintain a free list etc.
Richard Feldman (Jul 16 2024 at 03:13):it sounds complicated, but all the allocations are exactly the same size, so the free list part should be straightforward
Brendan Hansknecht (Jul 16 2024 at 03:14):Oh, kinda like the the terrible allocator I wrote for roc-wasm4, but for same sized types only.
Brendan Hansknecht (Jul 16 2024 at 03:14):Also, I guess we would have to use smart page mapping to ensure everything is seen as sequential in memory
Brendan Hansknecht (Jul 16 2024 at 03:16):So the lazy way to do this would be an anonymous mmap of some stupid size to get contiguous memory. Treat it as a gigantic array of allocations and then have a free list.
Richard Feldman (Jul 16 2024 at 03:21):Brendan Hansknecht said:
Also, I guess we would have to use smart page mapping to ensure everything is seen as sequential in memory
I wasn't even thinking of that - rather, if you run out of the first mmap allocation (which seems really unlikely if we just virtual alloc like 2gb for it; that's a trivial fraction of 64-bit address space but would require mmap-ing a gazillion different files at once to exhaust), have the main allocator switch an enum over to "now we have a Vec of these instead of just one" and we iterate through them checking memory ranges on each dealloc
Richard Feldman (Jul 16 2024 at 03:22):so that would ~double the cost per dealloc if it actually came up (and otherwise the unhappy-path would be correctly branch predicted and ~free), but it would come up ~never except for pathological cases
Brendan Hansknecht (Jul 16 2024 at 03:23):Also, my allocator is terrible cause it deals with multiple sizes and is very naive to fit in a small space. I'm sure this will be a lot more sound and less terrible.
Richard Feldman (Jul 16 2024 at 03:24):and as a bonus, if it works for mmap it'll work for file descriptors (aka Streams, which still has some WIP API design work I haven't circled back to yet) too! :smiley:
Brendan Hansknecht (Jul 16 2024 at 03:25):Is there an advantage to the vector over just mapping like a terabyte or something else ridiculous and just never worrying about running out (will oom way before running out).
Luke Boswell (Jul 16 2024 at 03:27):I think we should add the ability to mmap a file in basic cli. It would be mmaped and passed to roc a seamless slice. This means no copy when loading data into roc.
Would that make something like this run really nicely? https://github.com/lukewilliamboswell/roc-htmx-tailwindcss-demo/blob/f42cabf79b32443662678cde5d809f8f7e918e61/app.roc#L247
Richard Feldman (Jul 16 2024 at 03:27):it's a good question - there's probably a math problem there haha...like if we do 1 of those for mmap and one of them for file descriptors, what if the application author wants to do one too?
Richard Feldman (Jul 16 2024 at 03:28):oh actually
Richard Feldman (Jul 16 2024 at 03:31):at least on UNIX, there are maximum of 2^31 FDs at once, and they're each 4B, so that's only 8gb
Richard Feldman (Jul 16 2024 at 03:31):apparently in Windows it's even smaller because they use 24-bit handles
Richard Feldman (Jul 16 2024 at 03:31):so yeah that simplifies it even more haha
Brendan Hansknecht (Jul 16 2024 at 03:31):@Luke Boswell it would definitely help some. I'm not sure the current state of basic webserver and data copying. I think last I checked, we always copy out of roc lists and into the response. We would need to fix that as well so the direct output to the network card from a roc list. But yeah, would be part of the picture to make that better.
Brendan Hansknecht (Jul 16 2024 at 04:21):2^31 FDs at once
Though for us due to boxing, we will be storing an (i64, i32). So roc can refcount the box.
Richard Feldman (Jul 16 2024 at 10:51):oh, true
Brendan Hansknecht (Jul 16 2024 at 15:56):Related to this, is there a reason that basic-cli uses Box<dyn CustomBuffered> instead of BufReader<File>?
Do we expect to mix buffered reader types? Like mix tcp streams and files? Otherwise, I think we can make each of these concrete.
Anton (Jul 16 2024 at 16:00):I think @Sam Mohr added that
Brendan Hansknecht (Jul 16 2024 at 16:22):To be fair, a box here is probably pretty low cost when copying from a buffer anyway.
Brendan Hansknecht (Jul 16 2024 at 16:23):So we probably could group various reader types together....oh, but you can't seek in a TCP Stream. So that cant be merged to the same CustomBuffered
Brendan Hansknecht (Jul 16 2024 at 18:39):Rust types are always so simple:
OnceLock<Mutex<RefCell<Heap<BufReader<File>>>>>
Brendan Hansknecht (Jul 16 2024 at 18:39):Goal is to make as long of a >>>>> as possible, right?
Brendan Hansknecht (Jul 16 2024 at 20:19):Automatic file closing is actually pretty simple overall:
https://github.com/roc-lang/basic-cli/compare/refactor-host...automatic-file-closing
Brendan Hansknecht (Jul 16 2024 at 21:01):So @Richard Feldman, I am thinking that for basic-cli, there will be 4 of these heaps:
That said, not sold on 4 at the moment. Fundamentally, I want to load Str and List U8 from the platform without an extra copy. We have 2 options for that:
read_to_end and read_line that take a RocList<u8> as the buffer and are smart enough to fill it inplace.read_to_end and read_line, but turn the resulting Vec<u8> into a seamless slice that roc can access. Would require a heap of (usize, Vec<u8>) that frees the vec when roc thinks it is freeing the underlying list. Brendan Hansknecht (Jul 16 2024 at 21:04):Note: TCPStream and File could be merged today, but the moment we support seeking, it won't be valid anymore.
Richard Feldman (Jul 16 2024 at 21:12):I'd personally go for 1
Richard Feldman (Jul 16 2024 at 21:13):seems simpler than having an extra heap that has to deal with arbitrary sizes (unlike the other 2)
Brendan Hansknecht (Jul 16 2024 at 21:13):Won't be dealing with the different sizes. It will just be holding a vector. Rust allocator would allocate for the bytes.
Brendan Hansknecht (Jul 16 2024 at 21:14):I think 2 would actually be quicker to implement, but 1 is better cause a real list is passed back to roc. So it could be extended. Both could be mutated in place though.
Brendan Hansknecht (Jul 16 2024 at 21:24):Oh also, I guess would could put more things in one heap at the cost of element size (or safety). Just use a tag union or a raw union for the values.
Richard Feldman (Jul 16 2024 at 23:01):true!
Brendan Hansknecht (Jul 16 2024 at 23:46):How should we surface running out of heap space to a user? Just like a no more file handles available error?
Richard Feldman (Jul 17 2024 at 00:02):is that possible if we're doing the big virtual allocation up front?
Brendan Hansknecht (Jul 17 2024 at 00:04):Depends on how big "big" is. I arbitrarily just made it 65536 for now, but I can make it a full 2^31 or something like that.
Richard Feldman (Jul 17 2024 at 00:11):yeah I think making it "big enough that overflow can't happen" seems worth it, given the small amount of virtual address space it would use up and that it would make an error condition impossible!
Richard Feldman (Jul 17 2024 at 00:12):although as you noted earlier, it would actually need to be u32::MAX * size_of::<(u32, usize)> for the refcount, assuming they're stored side by side
Richard Feldman (Jul 17 2024 at 00:12):which is unfortunate because of alignment
Brendan Hansknecht (Jul 17 2024 at 00:13):There is one caveat (that probably doesn't matter in practice cause you will OOM), but technically a user can open infinite mmap or files. Cause they could open the same file a million times which is only 1 file handle.
Richard Feldman (Jul 17 2024 at 00:14)::thinking: is that how that works?
Richard Feldman (Jul 17 2024 at 00:14):will the OS give back the same fd every time?
Brendan Hansknecht (Jul 17 2024 at 00:14):So having 2^32 slots doesn't guarantee they won't all get filled
Brendan Hansknecht (Jul 17 2024 at 00:14):will the OS give back the same fd every time?
Maybe I am wrong for files, but I thought it could.
Brendan Hansknecht (Jul 17 2024 at 00:16):Also, this is actually more than a (u32, usize) due to BufReader.
Really will be:
(usize, {{Box<u8>, usize, usize, usize}, u32})
Perplexity says you get new ones
Brendan Hansknecht (Jul 17 2024 at 00:17):Ok, so not an issue with file descriptors.
Richard Feldman (Jul 17 2024 at 00:18):ok so about 200gb
edit: 1.6 TB, forgot to multiply by size_of::<usize> originally
Richard Feldman (Jul 17 2024 at 00:18):(6 * 8 * 2^32)
Brendan Hansknecht (Jul 17 2024 at 00:19):So in the realm of doable even on a desktop. Just add enough swap
Richard Feldman (Jul 17 2024 at 00:19):out of the address space of 2^48 on a 64-bit system
Brendan Hansknecht (Jul 17 2024 at 00:20):Very true, still table scraps compared to 2^48. So, will just size it for the max size.
Richard Feldman (Jul 17 2024 at 00:21):sounds good! :thumbs_up:
Brendan Hansknecht (Jul 17 2024 at 00:22):If people start using millions of connections at once, we may need to rethink our strategy to allow eventually freeing pages from the mmap to avoid the cost that memory, but definitely not a now problem
Brendan Hansknecht (Jul 17 2024 at 00:30):Oh also, for mmaping a file, any thoughts on configuration:
Probably can be configurable in userland to some extent. Just curious in one is seen as specifically valuable. I add assumed copy on write by default. So it becomes scratch space for the user once the file is loaded...
Luke Boswell (Jul 17 2024 at 00:31):If people start using millions of connections at once, we may need to rethink our strategy
:mind_blown:
Brendan Hansknecht (Jul 17 2024 at 00:32):Also, I'm not sure we can make it read-only and have it automatically free....might be a limitation of current seamless slices. To make it auto free, the refcount has to be 1 such that roc can free it. To make it read only, refcount needs to be at least 2 to ensure roc doesn't write to it.
Richard Feldman (Jul 17 2024 at 01:21):the FD could have its own refcount separate from the List
Richard Feldman (Jul 17 2024 at 01:22):and then we could store on the heap next to the FD a pointer to the list's allocation
Richard Feldman (Jul 17 2024 at 01:23):so when we dealloc the FD we give the list's refcount an extra decrement
Richard Feldman (Jul 17 2024 at 01:23):enabling it to go down to 0 again
Brendan Hansknecht (Jul 17 2024 at 01:25):But what keeps the FD alive?
Like once I run mmap and get back a List U8, I probably will drop the file in roc?
Richard Feldman (Jul 17 2024 at 01:29):oh hm good point
Richard Feldman (Jul 17 2024 at 01:32):wait aren't slices always readonly regardless of refcount?
Brendan Hansknecht (Jul 17 2024 at 01:33):I honestly don't recall, but I thought the could be mutated in place if they have unique ownership. They can grow without a realloc, but they can subslice and mutate in place.
Richard Feldman (Jul 17 2024 at 01:34):hm
Richard Feldman (Jul 17 2024 at 01:35):yeah I guess it would make sense that they could, for use cases other than this one :laughing:
Brendan Hansknecht (Jul 17 2024 at 01:36):If we really wanted, we could steal an extra bit from the original allocation pointer for this.
Richard Feldman (Jul 17 2024 at 01:37):yeah I was thinking about some sort of bit packing
Richard Feldman (Jul 17 2024 at 01:37):extra instruction or two for a lot of operations though
Brendan Hansknecht (Jul 17 2024 at 01:38):Also, I just realized
write-back
This doesn't make sense in roc. Cause if you do any tranformation that accidentally clones or duplicates the list, you will lose the original allocation.
Brendan Hansknecht (Jul 17 2024 at 01:38):So obviously can't write back.
Brendan Hansknecht (Jul 17 2024 at 01:38):At least not with a List U8. Would need a different api.
Richard Feldman (Jul 17 2024 at 01:38):oh true haha
Brendan Hansknecht (Jul 17 2024 at 01:39):So I guess my current vote is, lets just make it a mutable copy-on-write mmap. Then if the user happens to write, it doesn't matter and everything will get cleaned up happily.
Brendan Hansknecht (Jul 17 2024 at 01:40):Also avoids needing extra special handling or adding an extra bit to slices related to write permissions.
Brendan Hansknecht (Jul 17 2024 at 01:43):And yeah, using an extra bit for this would mean that every uniqueness check in roc for list/str would need to be for both uniqueness and for writeablity. So that would really be everywhere. That said, I think we could steal the highest bit of the refcount in general for this and it would be mostly fine. Like I think we could still keep the checks minimal, but it would be inconvenient to set that all up.
Richard Feldman (Jul 17 2024 at 01:44):makes sense to me! :+1:
Brendan Hansknecht (Jul 17 2024 at 02:27):I guess I can't just giant mmap with default linux settings:
0Heuristic overcommit handling. Obvious overcommits of address space are refused. Used for a typical system. It ensures a seriously wild allocation fails while allowing overcommit to reduce swap usage. root is allowed to allocate slightly more memory in this mode. This is the default.
Richard Feldman (Jul 17 2024 at 10:49):ahh that's a shame
Luke Boswell (Jul 18 2024 at 00:43):Is it possible to replace the old API, so instead of having File.mmap and File.readBytes we just have the one? the name mmap isn't very clear from a new user's perspective
Luke Boswell (Jul 18 2024 at 00:43):And how does this play with the FileReader handle?
Brendan Hansknecht (Jul 18 2024 at 00:45):And how does this play with the
FileReaderhandle?
It doesn't. It is just a separate api. I debated making it work with the FileReader, but I don't think that makes sense unless we separate the File from the BufReader.
Luke Boswell (Jul 18 2024 at 00:46):I'm a little confused here, just looking from the API in File.roc alone. It looks like we have 3 different ways of doing things
Brendan Hansknecht (Jul 18 2024 at 00:47):If you look at most file apis, that is the norm, but maybe we should reduce
Brendan Hansknecht (Jul 18 2024 at 00:47):Fundamentally, they all have different performance characteristics and tradeoffs
Luke Boswell (Jul 18 2024 at 00:47):I'm not really understanding why we want/need three
Luke Boswell (Jul 18 2024 at 00:49):So does mmap not open the file or something?
Luke Boswell (Jul 18 2024 at 00:50):It seems like the mmap is the superior thing here and does everything the others do but better.
Luke Boswell (Jul 18 2024 at 00:51):It's lazy so doesn't actually touch the data until needed. It can read buffered. It auto drops the file (closes) when it's no longer required by roc
Luke Boswell (Jul 18 2024 at 00:51):My current thought is "why not just have mmap do everything?"
Brendan Hansknecht (Jul 18 2024 at 01:04):So we definitely need at least 2 things:
Brendan Hansknecht (Jul 18 2024 at 01:08):Also, the mmap technically has potential sharp edges that the kernel defines as unspecified behaviour. So not necessarily something we should give to new users unless they learn a little first.
Luke Boswell (Jul 18 2024 at 01:14):So can you pass that List U8 all around your program and as long as you don't mutate it there are no copies?
Luke Boswell (Jul 18 2024 at 01:14):The data just might change from underneath you though, right?
Luke Boswell (Jul 18 2024 at 01:17):After spending some time reading the notes in File.roc and thinking about this I think we should keep it all the same as you have proposed in the PR.
I just think we should;
mmap to mapMemoryAdvanced, this will discourage users who don't just assume this is simple Brendan Hansknecht (Jul 18 2024 at 01:22):Yeah sharp edges with the mmap are:
Brendan Hansknecht (Jul 18 2024 at 01:23):Related rust doc:
All file-backed memory map constructors are marked
unsafebecause of the potential for Undefined Behavior (UB) using the map if the underlying file is subsequently modified, in or out of process. Applications must consider the risk and take appropriate precautions when using file-backed maps. Solutions such as file permissions, locks or process-private (e.g. unlinked) files exist but are platform specific and limited.
Luke Boswell (Jul 18 2024 at 01:25):I think this is really useful feature, and shows the power of the platform abstraction.
It does make me wish we had something like a debugging or analysis tool or an editor extension that would provide feedback on things like this. I imagine in my editor there's a flag that tells me if/where a List is mutated.
Brendan Hansknecht (Jul 18 2024 at 01:26):Also, I like the idea of renaming and adding more docs
Brendan Hansknecht (Jul 18 2024 at 01:32):pushed an update with docs and name change
Richard Feldman (Jul 19 2024 at 04:06):Brendan Hansknecht said:
This one I am not sure of, but theoretically if you have clean pages, the os could just dump them when memory pressure is high. By the time you go to read them again, the data may have changed. So it might be possible to get mutation in a roc list.
so reading up on this more, it seems like this can indeed happen - and I'd like to try to find an API that would prevent this from happening
Richard Feldman (Jul 19 2024 at 04:07):which would necessarily be something other than a List I think
Brendan Hansknecht (Jul 19 2024 at 04:08):I feel like it is best to call that a risk of mmap but leave it for perf. Cause sometimes mmap is the best interace
Brendan Hansknecht (Jul 19 2024 at 04:09):For ergonomic and/or perf
Brendan Hansknecht (Jul 19 2024 at 04:09):I guess I see it as a practical evil
Richard Feldman (Jul 19 2024 at 04:11):well we can use mmap under the hood but offer a safe API into it
Richard Feldman (Jul 19 2024 at 04:12):for example, we could have the call give you back an opaque type representing the mmap'd file, and it has all the List operations on it except they're all Task based
Richard Feldman (Jul 19 2024 at 04:15):I think an important peace of mind that Roc application authors should have is "if I look at the types, I know what error conditions can happen, and if there isn't an error possibility mentioned in the type, then the worst unhappy-path behavior that can happen is that it returns a different value than I was expecting, or else a crash"
Richard Feldman (Jul 19 2024 at 04:17):but like here we're talking about "this function returns a value which, if passed to another function, can make that function no longer pure"
Richard Feldman (Jul 19 2024 at 04:17):that is very well beyond "hey be extra careful with this one" :big_smile:
Richard Feldman (Jul 19 2024 at 04:18):but I think there's gotta be a way to get the perf benefits of mmap while keeping all the functions involved pure!
Richard Feldman (Jul 19 2024 at 04:20):for example, isn't the way mmap would most commonly be used in this way be for parsing?
Richard Feldman (Jul 19 2024 at 04:20):in that situation, we could use it as an implementation detail and offer a walk function to traverse the bytes
Richard Feldman (Jul 19 2024 at 04:21):at which point even if it does change in the middle of the walk, you're still seeing each byte only once, so the only consequence is that the contents of the file may seem strange
Richard Feldman (Jul 19 2024 at 04:22):but it wouldn't break any fundamental language guarantees like purity
Brendan Hansknecht (Jul 19 2024 at 04:26):Hmm...I think it would be able to work as an opaque wrapping a slice, but I don't think it would work as a task based opaque. Tasks will add too much overhead for byte based operations
Richard Feldman (Jul 19 2024 at 04:27):what about if it's just one walk?
Richard Feldman (Jul 19 2024 at 04:28):something like:
walkMapped : MappedStream, state, (state, U8 -> state) -> Task state *
so there's one Task to kick it off, but then that one task is just calling the (state, U8 -> state) function iteratively, exactly like a normal List.walk
Brendan Hansknecht (Jul 19 2024 at 04:29):I think that has two issues:
1, the closure will never be inlined
Richard Feldman (Jul 19 2024 at 04:30):for 1, the platform could still bring in the "unsafe list" exactly like today in the effect, just not expose it directly
Richard Feldman (Jul 19 2024 at 04:30):so then it could literally be calling List.walk after removing the opaque wrapper, so all inlining would happen as normal
Brendan Hansknecht (Jul 19 2024 at 04:30):Ah yeah.
Richard Feldman (Jul 19 2024 at 04:31):list pattern matching wouldn't work though, yeah, which would be unfortunate because it's so nice
Brendan Hansknecht (Jul 19 2024 at 04:31):I think you actually want a more powerful opaque type though. Basically a 1 way iterator opaque type. But like it still lets grab more elements at once instead of just a single item at a time.......
Richard Feldman (Jul 19 2024 at 04:32):that would be possible, although I can't think of a way to avoid it having to heap-allocate each of those lists
Brendan Hansknecht (Jul 19 2024 at 04:34):The horrible but should work solution....every request for a chunk of the list, read a value and write a random value, then the same value back to it. That will mark the page as dirty. And stop it from ever going back to the file.
Brendan Hansknecht (Jul 19 2024 at 04:35):Do that once per page as part of the opaque under the hood then return the slice.
Richard Feldman (Jul 19 2024 at 04:36):would that hurt perf?
Richard Feldman (Jul 19 2024 at 04:36):if I understand it right, that would be triggering the MAP_PRIVATE copy on write
Richard Feldman (Jul 19 2024 at 04:36):which would result in an actual copy, yeah?
Brendan Hansknecht (Jul 19 2024 at 04:37):Hmm...I guess I'm not sure if the os can recognize a file is only open by one process and just give it ownership of the file instead of copying.
Brendan Hansknecht (Jul 19 2024 at 04:37):But yeah...not great
Brendan Hansknecht (Jul 19 2024 at 04:41):Trying to read up on file locking and permission things but don't currently see a good solution
Richard Feldman (Jul 19 2024 at 04:42):yeah from what I read, it seems like you need the other processes to cooperate
Richard Feldman (Jul 19 2024 at 04:42):to prevent it from happening
Brendan Hansknecht (Jul 19 2024 at 04:43):It's also extra inconvenient cause in practice for the programs most write with mmap, it isn't a concern. They are one off scripts on owned files.
Brendan Hansknecht (Jul 19 2024 at 04:44):And yeah, solution seem to be:
Brendan Hansknecht (Jul 19 2024 at 04:44):Or just accept it could go wrong
Brendan Hansknecht (Jul 19 2024 at 04:45):If there is a windows equivalent solution flock may be ok enough
Brendan Hansknecht (Jul 19 2024 at 04:46):Oh wait, flock looks to be in process
Brendan Hansknecht (Jul 19 2024 at 04:46):Nvm
Brendan Hansknecht (Jul 19 2024 at 04:52):Yeah, I guess my thought is that it might not be right for basic cli, but I think it is nice that roc has the flexibility to support it. Mmap on files is just fundamentally unsafe but also super useful at times.
Brendan Hansknecht (Jul 19 2024 at 05:21):Anyway, I think I am gonna look at some improvement to our line reading and buffering in basic-cli. Those should lead to a really nice baseline for solid io without mmap. right now, there is way to much copying.
Brendan Hansknecht (Jul 19 2024 at 16:22):Richard Feldman said:
what about if it's just one walk?
So this still has one major edge case, but maybe is more acceptable. If someone truncates or deletes the file, your program will crash during the walk when it tries to load a page that doesn't exist anymore.
Brendan Hansknecht (Jul 19 2024 at 16:51):Also, I removed mmap from https://github.com/roc-lang/basic-cli/pull/230
Instead, it now has some changes and improvements to buffered file reading.
Last updated: Jun 16 2026 at 16:19 UTC