20 ms·

When your data doesn’t fit in memory: the basic techniques

638 points by itamarst 7y ago

userbinator 7y ago
Unusual to have no occurrence of the word "stream" anywhere in the article... given that's the usual term for algorithms which require a constant or almost-constant space regardless of the amount of data they process. A semi-common beginning programmer's exercise is to write a program that numbers the lines in a text file. The naive solution will use O(n) space, while a bit more thought reveals that this can be done in constant (to be really precise, O(log n) where n is the number of lines in the file) space.
- itamarst 7y ago
  Chunking is the term I used because that's more relevant to the data science domain I'm focusing on here (e.g. Pandas has "chunksize", Zarr has "chunks"). Streaming has some implication of an ongoing stream of data to me... but I ought to clarify some of the assumptions about a fixed size of data, yes.
  - denhaus 7y ago
    Ditto. Python multiprocessing also uses “chunks” with a specified chunksize.
  - roter 7y ago
    netCDF, used for storing e.g. large multidimensional climate datasets, is also "chunked" through its HDF[0] backbone. The hard part for me is the "transpose" or "striding" problem. i.e. when the data is stored in a series of (x, y, z) files for a given hour, day, or month and I need a time series at a point. [0] https://en.wikipedia.org/wiki/Hierarchical_Data_Format https://en.wikipedia.org/wiki/Hierarchical_Data_Format
  - dmurray 7y ago
    Chunking and streaming are different things to me. Chunking means you get to process multiple rows of data at the same time, usually useful to take advantage of SIMD. Streaming means that the data is accessed in a single pass: once you compute the effect of a given row on your statistics, you never have to rewind to see it again. Many modern performant solutions will use both, but they're not the same thing.
    - nine_k 7y ago
      One important application of chunking is efficient I/O. Mass storage is most efficient when doing large sequential reads and writes, so you normally feed your constant-space streaming algorithms from buffers with a large number of input records. Sometimes you can just tell the OS do efficient chunking prefetch for you.
      - hofstee 7y ago
        If you're streaming in a language like Python, its IO will be doing some degree of chunking behind the scenes. It might be beneficial to do more manually.
      - Sean1708 7y ago
        Often called buffering when applied to IO.
  - pythonwutang 7y ago
    > Chunking is the term I used because that's more relevant to the data science If your intended audience are data scientists then why didn’t you mention Dask?
- mytailorisrich 7y ago
  > A semi-common beginning programmer's exercise is to write a program that numbers the lines in a text file. In term of RAM this can be done an arbitrarily small buffer in the sense that this can be done by reading the file byte by byte. I.e. O(1). Edit: For all practical purposes the line counter is also constant space.
  - rongenre 7y ago
    Yeah log(n) would be the space to hold the digits of the counter. Presumably (unless things got super-silly), this would be dominated by the buffer size for the line being read.
    - dfox 7y ago
      The point there is that you don’t need a buffer for whole line, you only have to find the line terminators. Something like: printf(“0: “); ln = 1; while ((ch = getch()) != EOF) { putch(ch); if (ch == EOL) { printf(“%d: “, ln); ln++; } } And I believe that original unix implementation of nl is mostly this, although with the stdio functions replaced with raw read/write.
  - johnc1231 7y ago
    Yeah, I think the above poster said O(logn) space because that's the size of the line count in bits
    - jeremysalwen 7y ago
      The usual computation model includes "log n sized words", so it really is O (1). You usually are implicitly using that model, otherwise any algorithm that used pointers would have an extra log n tacked on, e.g. linked lists append would be log n not constant.
- gwbas1c 7y ago
  > Unusual to have no occurrence of the word "stream" anywhere in the article... Or "database"
  - nautilus12 7y ago
    Both indicators (along with python) that this is an article written by a yet another data scientist that thinks engineering is unecessary. Data science is a field that is plagued by individuals having very specific narrow experiences that are often easy to engineer making them think they are experts in data engineering. Vertical scalability has a hard bound, if your algorithm changes complexity it could become literally impossible to move forward. Horizontal scalability gives you options, this is why we like it, not just because we like to overengineer systems, but because we don't like embracing hard limitations on the systems we engineer, especially when we often don't know yet what problem we are solving. Engineers often don't get the liberty of solving extremely specific instances of problems like data scientists do.
    - realusername 7y ago
      > Data science is a field that is plagued by individuals having very specific narrow experiences that are often easy to engineer making them think they are experts in data engineering. That's on point, some of the worst and most inefficient code I had to maintain was written by data scientists. They are for sure leagues above any of my data science knowledge in their respective field but the average engineering knowledge and best practices seems pretty low.
    - deleted 7y ago
      [deleted]
    - kyllo 7y ago
      Most of the time it's not that data scientists think engineering is "unnecessary," it's that they're expected to deliver analyses and models without the help of engineers, because the engineers are on another team, behind a massive backlog. So they make do with the tools they have.
- rhinoceraptor 7y ago
  > write a program that numbers the lines in a text file Ah, simple :) cat file | wc -l
  - dyanaraps 7y ago
    Useless use of `cat`. :) wc -l file To hide filename: wc -l < file
    - scarejunba 7y ago
      I'm actually pretty much against UUoC. The cat example is much more resilient to modification. For instance, there are usually natural modifications considering filtering etc. Anyway, since he said number we probably want `nl` not `wc`. Separating pipe-setup from processing is sound engineering to me and makes things much easier. For instance as I iterate, I will have cat piped to head piped to filter but eventually I'll take the head out and run the whole thing. That's a trivial ^W versus moving around arguments and worrying about arg order, etc.
      - navaati 7y ago
        That's right regarding directly giving the filename for the program (here wc) to open itself. However using the input redirect is fine, especially if you format it that way (which is exactly the same thing): <file wc -l Then, adding another step is as natural as with cat: <file grep meh |wc -l
        thestoicattack 7y ago
        Useless use of `wc` :) <file grep -c meh
        deleted 7y ago
        [deleted]
        herpderperator 7y ago
- diabeetusman 7y ago
  Sorry, isn't there quite a bit of a difference between O(1) and O(log N) space? My first inclination would be to have a counter at zero, read in a line, write out the counter then write out the line, then increment the counter. The space complexity here is O(1), is it not?
  - yifanl 7y ago
    Storing the number n takes log n bits, if we're being super pedantic :)
    - thfuran 7y ago
      In practice, I'd say it takes exactly 64 bits for any file.
      - MiroF 7y ago
        Asymptotic notation isn't about what's "in practice." We have very good asymptotic complexity for multiplication, but don't use the ones that scale the closest to linear because the time constant is enormous.
        dfox 7y ago
        With the O() notation the units are some arbitrary computation step or arbitrary unit of memory, which could even mean matrix multiplication of two 1024x1024 matrices of doubles. The whole point of big-O notation is that you don’t care about how fast/expensive it is, but how it scales.
        MiroF 7y ago
        Yes and the memory to store a number scales with the log of the number
        darkmighty 7y ago
        There are different models of computation. You can have a model in which integers can be arbitrarily large yet still count as constant memory (for analyzing practical-size algorithms on 64-bit machines, for example); I'm not sure how common those are. I know for example arithmetic is often assumed to be constant time (it indeed varies by input size, even x=y+1, which is clearly O(log(y))). Also relevant here is the RAM machine model that is often employed, where you can have essentially unlimited memory that can be randomly accessed at fixed time. This again is roughly in line with real practical machines running algorithms that use, and fit within RAM. In reality if you wanted a more physically consistent model eventually your access times must differentiate and increase for increasing memory -- data occupies physical space and must be fetched at increasingly long distances, limited by the speed of light. In principle this means m bits of memory at best can be accessed in O(m^(1/3)) time [1]. Of course, this realism isn't always practically relevant (maybe for datacenter-scale problems, perhaps even larger) and complicates the analysis of algorithms. [1]: Just for fun, if you want to get really physically accurate, this isn't quite right either I suspect -- that's because with enough data (physical bits) occupying a volume at constant density it will eventually collapse into a black hole, which kinda destroys your computer :). So for planetary-scale computers you eventually need to spread your data across a disk, like a small galaxy (or Discworld, if you prefer :)), so it won't collapse, giving it O(sqrt(m)) access time. Surprise, very large worlds must be flat. This is related to the BH entropy formula, and the so called Holographic principle, I guess -- the entropy and hence information content of a volume is surprisingly bounded by its area, since a Black Hole's area is proportional to its mass. The weird thing of course is how the universe itself perhaps should collapse to a black hole since it has a lot of stuff in any sufficiently large volume, being young and dynamic it hasn't happened yet. It's alsogiven by its fractal scale, but I guess this digression has grown large enough already :) (do tell if you want to learn more)
- tehsauce 7y ago
  O(log n) is not constant
  - mark-r 7y ago
    I think the point in this case is that log n has a reasonable upper bound, and can be considered constant for any real world problem.
- WanderPanda 7y ago
  O(log n) is so precise it ain't even informative :P
- bogomipz 7y ago
  >The naive solution will use O(n) space, while a bit more thought reveals that this can be done in constant (to be really precise, O(log n) where n is the number of lines in the file) space" Can you elaborate on the O(1) solution?
  - xondono 7y ago
    Not an expert, but after reading around OP is saying you only need a constant sized buffer (that could be as little as a character deep) to read the whole file looking for line breaks. This roughly takes O(1) space (A lot of commenters are confusing time vs space requirements) but there's a little nitpick to be found, in extremely big files the line counter itself would be O(log(n)) and would dominate.
    - bogomipz 7y ago
      I see, yes that makes sense. The conflation with time instead of space was confusing me. Thanks.
- tmh88j 7y ago
  >A semi-common beginning programmer's exercise is to write a program that numbers the lines in a text file. The naive solution will use O(n) space, while a bit more thought reveals that this can be done in constant (to be really precise, O(log n) where n is the number of lines in the file) space. I guess I'm misinterpreting the task, because I'm having trouble seeing how it's possible to access each line in a file without it being O(n) at a minimum. I understand O(log n) to mean that not every data point is "accessed" due to the way the data structure is organized, lines of a file in this case, but to me it appears that not every line would be prepended with a number. My instinct is that there's a lot going on with new lines/line breaks in files that I'm not aware of, so I'd really appreciate any reading material on the subject to help me better understand this. Thanks!
  - unlivingthing 7y ago
    I think you've got confused with O(n) time; that is the amount of memory that is needed and not the time required to access a particular line.
    - tmh88j 7y ago
      Good point, I was thinking in terms of time complexity rather than space, but the title clearly is in reference to memory. I guess that explains my confusion!
    - profmonocle 7y ago
      I made the same mistake at first, had to reread the post. I'm so used to seeing Big O notation used for time that I guess my eyes just passed over the word "space". (My mistake obviously, the OP was very clear.)
- 3xblah 7y ago
  sed = 1.txt Use small buffer. No need to fit all the data into memory.
- kashif 7y ago
  I was also surprised by the lack of streaming. In Python specifically for really large JSON datasets I wrote this streamer that many have found useful - https://github.com/kashifrazzaqui/json-streamer https://github.com/kashifrazzaqui/json-streamer
- deleted 7y ago
  [deleted]
Sahonon 7y ago
Dumb question, but wouldn't memory mapping or lazy/streaming processing (e.g. SAX for parsing large XML documents, Java Streams for handling large amounts of "things", memory mapped files for anything you don't need intermediate representations for) resolve this problem as well?
- itamarst 7y ago
  See above about streaming (chunking is basically the same thing). mmaping is a form of uncontrolled chunking, where chunk size and location is determined by operating system's filesytem caching policy, readahead heuristics, and the like. As a result, it can sometimes have much worse performance than an explicit chunking strategy, especially if you just treat it as magic. Or to put it another way, mmaping is helpful but you still need to understand why it might help and how to use it.
  - faizshah 7y ago
    > it can sometimes have much worse performance than an explicit chunking strategy Can you expand on this? I haven’t heard this before. Edit: Found a comprehensive discussion on this https://stackoverflow.com/questions/45972/mmap-vs-reading-blocks https://stackoverflow.com/questions/45972/mmap-vs-reading-bl...
amoron 7y ago
I would just cat | grep | awk | sed on this stuff rather than resorting to Py.
- j88439h84 7y ago
  Awk pipelines are exactly the area where Mario is useful for Python programmers. https://github.com/python-mario/mario https://github.com/python-mario/mario
wongarsu 7y ago
Another key technique I've used is to use pipes and basic command line tools where possible to pre- or postprocess your data. For example a `sort | uniq -c | sort -nr | head` pipeline to get only the most frequently occurring lines works in a few kilobytes of ram no matter how big the input is. Combine this with chunking and you can get a lot of data processed in manageable amounts of memory. Of course the next problem is "my data doesn't fit on disk", but with xzcat on the command line and lzma.open in python you can work transparently with compressed files.
- vardump 7y ago
  > Of course the next problem is "my data doesn't fit on disk", but with xzcat on the command line and lzma.open in python you can work transparently with compressed files. I usually use LZ4 compression for this purpose, because it's ridiculously fast (700 MB/s per core compression and 5 GB/s decompression). Sure, compression ratios aren't as good, but usually good enough.
- muxator 7y ago
  Completely agree (I do this myself all the time) but keeo in mind the initial sort has not a constant cost in term of memory. Yet, one realizes how well written these basic tools are only after having some bruises with fancier tools.
  - wongarsu 7y ago
    I don't know what POSIX says on the matter, but at least GNU sort uses some variation of merge sort with temporary files and has for all intents and purposes constant memory use.
- naniwaduni 7y ago
  Compression alleviates the problems "my current disks don't fit my data" and "my data is too big for my disk quota". It's comparatively bad at solving the problem "I cannot buy enough disks to fit my data".
- namibj 7y ago
  zstd is nearly always superior to xz, fyi.
RcouF1uZ4gsC 7y ago
> The easiest solution to not having enough RAM is to throw money at the problem. People underestimate how much memory modern computers can actually support if you max them out. http://www.itu.dk/people/jovt/fitinram/ http://www.itu.dk/people/jovt/fitinram/
- wongarsu 7y ago
  And not just on super fancy computers, 128GB of RAM is like $500 and is supported by many low-to-mid-range desktop systems.
  - kevin_thibedeau 7y ago
    Without ECC that's a risky way to compute.
    - ben-schaaf 7y ago
      IIRC ryzen in general can run with ecc, though motherboard support is a little shaky
    - wongarsu 7y ago
      Eyeballing the numbers [0][1] I would expect one bitflip between once every year and once every 100 years on 128GB of memory. I'm willing to take those odds. Of course with some planning you can get an AMD system with ECC support on the mainboard; ECC RAM is about the same price as consumer RAM. 0: https://www.cs.toronto.edu/~bianca/papers/sigmetrics09.pdf https://www.cs.toronto.edu/~bianca/papers/sigmetrics09.pdf 1: https://www.cs.virginia.edu/~gurumurthi/papers/asplos15.pdf https://www.cs.virginia.edu/~gurumurthi/papers/asplos15.pdf
      - nostrademons 7y ago
        When Craig Silverstein left Google somebody asked him "What was the biggest mistake you made while at Google?" His response was "Not using ECC memory." The problem is that both the consequences and debugging time of a single random bitflip are potentially unbounded. That time that GMail lost 10% of their accounts and had to restore from tape was because of a single bitflip (due to a software bug, not a cosmic ray). Google Search lost months of engineering time in the early days from cosmic rays, back when they really could've used those engineers on other stuff. The odds may be low, but they do happen when you have multiple computers, and the consequences are high. Not really odds I'd want to take, when ECC RAM isn't that much more expensive than non-ECC RAM.
threeseed 7y ago
You can spin up a standalone Spark cluster in about an hour and it's pretty easy. And yes you will need to rewrite a small amount of your code but you're doing so here as well. At least you will be able to scale out to much larger volumes in a consistent way.
- zaphar 7y ago
  For many tasks a spark cluster is overkill. Streaming will get you a really long way before you have to tackle running a while spark cluster. And you'll probably be able to still do it on your laptop.
  - threeseed 7y ago
    You can't just apply a streaming paradigm to a batch style workload. And 90% of all tasks are batch orientated.
    - zaphar 7y ago
      Batch is just streaming in really large chunks. And besides if you are messing around with data on your laptop you probably aren't at the stage of working out a batch workload yet. Jumping immediately to this needs to be a batch workload before you have had a chance to play with it is probably overkill.
cosmic_quanta 7y ago
I wrote a library to deal with this problem when it comes to NumPy arrays (e.g. images). Could not fit all images in RAM, so I went with a constant-memory approach[0]. The reduction in memory has allowed us to do parallel processing, for a pretty significant speed-up! [0](github.com/LaurentRDC/npstreams)
gwbas1c 7y ago
> When your data doesn’t fit in memory: the basic techniques Uhm... Isn't it called a database? Jokes aside, one of the core use cases of things like databases is random access to a part of data that's too large to fit in RAM.
- dev_dull 7y ago
  My assumption was that the system had finite ram available, whether that's serialized in a database or read directly into the program.
  - gwbas1c 7y ago
    So? Typically "database" implies a product like SQLite or Postgres. These handle many multiples of RAM size. In-memory databases are a thing, but that's a very specialized use case.
    - dfox 7y ago
      Somewhat surprising fact about most PostgreSQL deployments is that most of the frequently accessed tuples will fit into RAM and it handles this usecase really well (to the extent that people who don’t know any better do not see any issue with LIKE ‘%whatewer%’ over 100M tuple table, it just takes 1.5s, so what...)
  - PhearTheCeal 7y ago
    Pretty much all SQL DBs support pagination, and many libraries that abstract the DB away hide this as an iterator.
- VikingCoder 7y ago
  Hi, once upon a time, I worked with medical image data. I literally had a DBA suggest storing the volumetric data in a database. I worked to diligently to explain to him why he was incorrect. When he resisted my explanations and tried to push forward with his plan, I worked diligently to get him fired. I was successful.
xiaodai 7y ago
Use Dask. In R for tabular data use disk.frame
floki999 7y ago
Dask anyone? Allowed me to handle a 60 Gb dataset on a machine with 16 Gb RAM. High level of compatibility with Pandas dataframes.
- xiaodai 7y ago
  I mean, don't reach for Spark. Just get Dask, a databased or R's disk.frame is mostly fine.
- roaur 7y ago
  I'm a Dask evangelist. It's a remarkable tool and is one of the first I reach for when this problem arises. Maybe it's not well known?
wooly_bully 7y ago
The "spin up a big data cluster" bit at the beginning seems like either a straw man or just oddly out of touch. Who, when determining how to process something on the order of a 100gb file, even considered something like that? Also, SQLite is a first class citizen in this space. Most if not all languages can easily load data to it, virtually any language used for analysis can easily read from it, and it's file-based so there's no reason to spin up a server. Finding 100GB on disk is much easier than 100GB in ram.
- mumblemumble 7y ago
  Divide that file size by 10, and you're still in the range where I've had to argue that rolling out Spark is overkill.
  - zetazzed 7y ago
    People will disbelieve that, but it's absolutely true... I'll never forget the interview I did with an engineer who described an elaborate Hadoop-based solution to some past problem. When I asked him what type of data he was working with, he said, "Here, I'll show you," then whipped out his laptop and showed me a spreadsheet. It wasn't an extract of the data. It was literally a spreadsheet, manageable on a laptop, that he somehow decided needed a Hadoop cluster to process. (Also, who shows data from your current employer to a new prospective employer? Weird but true.)
    - mumblemumble 7y ago
      I had an interesting experience a while back where it came to light that I was working on the same problem as another team in the org (this was a huge multinational), so a meeting was arranged so we could compare notes. The other team was slightly shocked to see that I could train a model in a minute or two, where it took them an hour or two using essentially the same algorithm. They insisted that shouldn't be, because I was doing it on my laptop and they were using a high performance computing cluster. They of course wanted to know how my implementation could be so much faster despite running on only a single machine. I didn't have the heart to suggest that maybe it was because, not despite. Ironically, I also got the implementation done in a lot fewer person-hours. I just did a straight code-up of the algorithm in the paper, where they had to do a bunch of extra work to figure out how to adapt it to scale-out. This isn't to say that big data doesn't happen. Just that it's a bit like sex in high school: People talk about it a lot more than they actually have it, perhaps because everyone's afraid their friends will find out they don't have it.
zneveu 7y ago
Another easy solution I didn't see mentioned is to create swap space on Linux. This obviously isn't the fastest solution, but setting up 128GB of swap space let's me mindlessly load most datasets into memory without a single code change.
- yummypaint 7y ago
  Do you have a sense of how the performance would compare to chunking? My naive expectation is that loading data from disk to swapped memory involves writing that data to disk (even if it will only be read).
  - wongarsu 7y ago
    Chunking can speed up processing even if the dataset fits into memory because you are interleaving disk reads and computation and the OS is likely to prefetch the next chunk into the read cache while you're still busy computing. On other problems chunking doesn't work at all and just mmaping or dedicating giant amounts of swap are better strategies. It depends on the problem at hand
- olavgg 7y ago
  Adding a 280GB Optane as swap is very efficient and cheap. It is still a lot slower than RAM though. But much much faster than NVME ssd's
  - p1esk 7y ago
    Are you talking about Optane NVDIMM or NVME?
- Rafuino 7y ago
  Plus, swap performance is being improved bit by bit, so it's not as much of a dirty word as it was before. https://lwn.net/Articles/717707/ https://lwn.net/Articles/717707/
- oxplot 7y ago
  This! It's simple, performant depending on application and costs zero in extra development.
__sy__ 7y ago
Just wanted to chime in to say that the Tensorflow 2.0 Dataset Library is nice for this sort of problem. It supports batching, caching, remote fetching, multiple cpu core splitting...etc.
onikolas7 7y ago
Fun fact for non CS people, which this article seems to address. Nothing fits: disk to RAM, RAM to L3, L3 to L2, L2 to L1, L1 to registers. We are just lucky that many programs have spatial and temporal locality.
- bufferoverflow 7y ago
  It looks like disk and RAM will merge soon into some form of insanely fast and persistent storage. And L3 is already at 256MB (+32MB L2) in the new AMD Threadripper CPUs.
daveslash 7y ago
The article mentsions Rent a VM in the cloud, with 64 cores and 432GB RAM, for $3.62/hour.. Does anyone have specific services they'd recommend?
- Aperocky 7y ago
  Plenty of options in the price range/ spec range for AWS: https://aws.amazon.com/ec2/pricing/on-demand/ https://aws.amazon.com/ec2/pricing/on-demand/ If you sign up by month it will be much cheaper too.
- kathrynloving 7y ago
  I'm working on a new platform to easily deploy compute/memory-intensive applications to cloud API endpoints [1]. This let's you share your app with others (e.g. colleagues) and makes the most sense if your task needs a lot of memory/CPU but not too much IO. Contact info is in my profile and I'm happy to discuss your use case! [1] https://www https://www explorablelabs.com
  - pojzon 7y ago
    You mean like terraform using predefined ami >_>?
scottlocklin 7y ago
^f mmap yeah, that's what I thought.
eggie5 7y ago
one word: Dask
elchief 7y ago
Ah yes. A problem they solved 50 years ago
- hinkley 7y ago
  We are about 5 years out from that being true for pretty much everything. Most of the problems we fight over were identified by the early 70's.
anotherevan 7y ago
The nice thing about virtual memory is you can make really big RAM disks…
- gowld 7y ago
  Isn't that a regular disk, with your OS's (or SSHD's) file cache?
  - mbreese 7y ago
    No, in this context, it's creating a virtual disk using only RAM as a backing store. If you do this, then you can use whatever tools you'd normally use (cat, wc, grep, etc) to explore a dataset as if they were files. It's the super quick and dirty way to go if you don't want to code up a proper solution and your data fits in RAM. (assuming the data is organized in files to begin with)
hamsham 7y ago
I recently ran into an issue in a game where my team and I were storing hundreds of 160-byte config structures in memory. It blew up to over 86kb of data (which doesn't seem like much, but we're already pressed for memory at a 64mb-limit). I compressed the configs by packing the structure into a 2-byte bitfield, simply twiddling bits to get/set each parameter, and just like that the 86 kilobyte configs dropped to just over 1kb. We're still trying to reduce memory elsewhere but the savings showed we can do similar tricks to significantly save our memory footprint in other places.
baybal2 7y ago
I think the author completely misses a mention that sequential access to cold store is nowhere as slow as access to ram. Cold store looses big in only scenarios where you have sequential and completely random seek patterns, and there are lots of way to optimise that in read and write heavy workloads. This was the art of running performant multi-terabyte DBs in a world prior to SSDs and ramdisks. For very big index walks, you want to have data to be more flat, and seeks to be sorted, so there is higher chance that needed records would be accessed without page eviction. Modern DBs, I believe, do something like that internally. And for write heavy loads, there is no alternative to revising "data structures 101." You can reduce the disk load by may times over with a properly picked tree, graph, or log structure.
- lichtenberger 7y ago
  Just wanted to add that tree and graph structures of course can be stored sequentially on disk or a flash drive (log-structured). For instance with a really fast random access storage and some additional space you can even save the history, that is lightweight snapshots of your data. That is you always append data. This way you can also use clever versioning algorithms to predict the performance (no read or write peaks) and to lower the space consumption.
- vikiomega9 7y ago
  Do you a list of required reading?
cpa 7y ago
A few years ago, I found surprisingly difficult to sort a file that didn't fit in RAM in Python; I couldn't find any simple libraries for this kind of stuff. Disappointingly, I ended up writing my data to a text file, sorting with unix sort (w/ some tuning on --parallel and --buffer-size) and reading it back.
- madhadron 7y ago
  > Disappointingly, I ended up writing my data to a text file, sorting with unix sort (w/ some tuning on --parallel and --buffer-size) and reading it back. One of my biggest beefs with Unix is that so much powerful functionality is locked up in command line utilities and not accessible as libraries.
longemen3000 7y ago
Im following closely the development on an alternative to data.frame that works on disk (disk.frame),using the same API
lllr_finger 7y ago
Binary serialization and real-time compression like zstd have opened up a whole new world for me. Something like flatbuffer even lets you index into structured data without a deserialization penalty.
- SlowRobotAhead 7y ago
  I’m also a fan of serialization that allows for streaming and in-memory access without fully deserializing. The project I’m working on uses CBOR and it’s been working really well. Not using the streaming, but being able to quickly access without transforming the data has been huge.
lmilcin 7y ago
mmap() anyone? Seriously, this should be the top of the list and default solution when you need to process large file that does not fit in memory. The exceptions would be when you can read the file once (then stream might be easier but not cheaper), when you don't want to rely on FS cage (you need your own) or when you need easy interoperability between different OS-es.
- jdmoreira 7y ago
  I came to the comments after reading the article just to find the person suggesting mmap and upvote them :)
  - neop1x 7y ago
    Exactly! Me too :D
    - lmilcin 7y ago
      It is quite saddening for me that so few developers try to take advantage of the tools available. It is really magical thing to be able to run just a single function and have your entire terabyte file suddenly present itself as addressable continuous memory space ripe for random access. Regular random access file I/O seems silly to me, like trying to work with the file through a key hole. Have you ever seen how ships are built inside a bottle? That's exactly the picture I have in my mind...
beached_whale 7y ago
mmap can really help with this too. It won't stop you from being silly and using random memory access patterns, but it does abstract away the file access as a piece of address space. Short of running on a 32bit machine, this can help a lot. Even on a 32bit machine you can abstract it away with another later and window the access.
gowld 7y ago
Not perl? I'm compelled to respond with "OK Boomer".
blueyes 7y ago
Since this is an article about speed and data processing on a Python blog, I'll just point out that the RiseLab team that created Ray and RLlib also has a library called Modin, which is distributed Pandas. You just import modin as pd without changing the code: https://github.com/modin-project/modin https://github.com/modin-project/modin
- jszymborski 7y ago
  and in that vein, Dask: https://dask.org/ https://dask.org/
- marcinzm 7y ago
  It will, however, from my reading convert the data to an actual pandas dataframe for certain operations. Which presumably is bad if your data doesn't fit into memory.
opdahl 7y ago
I'm currently running an index that requires over 64GB of ram. There's no possibility of lowering this, but I don't have a really high requirement for latency. So my solution was to get an M2 storage instance and create a 100GB swap space. Works like a charm and in the future, if I need the higher latency I just change the instance to something that has enough ram.
emmelaich 7y ago
There's an enormous amount of literature and technique in the mainframe world for dealing with data bigger than ram. Because that was the norm. Whole companies have been built around the problem. e.g. syncsort.com I hope some interesting techniques don't get locked up and lost in proprietry mainframe software.
cozzyd 7y ago
Here's where ROOT really shines
RivieraKid 7y ago
Another one: reservoir sampling. It's used in Deep CFR, a form of CFR that uses neural networks. CFR is an algorithm used for finding equilibrium strategies in imperfect information games, most notably poker. https://en.wikipedia.org/wiki/Reservoir_sampling https://en.wikipedia.org/wiki/Reservoir_sampling
lichtenberger 7y ago
I'm working on storing data in a log-structure persistently without the overhead of a transaction log in my spare time (Open Source[1]). Instead, an UberPage which guarantees consistency is atomically swapped during a transaction commit (inspired by ZFS). It should be used for data, which doesn't fit into main memory. Revisions are always appended, whereas almost only changed data plus some metadata is written to a file during commits. You can easily retain the full version history in a log structure, but you need fast random access (option of parallel "real" access would be best) on a flash drive -- PCIe SSDs for instance. Basically in order to balance read and write performance only a fraction of each database page (with changed records) needs to be written sequentially in batches to the end of a file. Each revision is indexed under a RevisionRootPage and these are indexed under the UberPage with keyed tries. This opens up a lot of opportunities for analysing data and its history. [1] https://github.com/sirixdb/sirix https://github.com/sirixdb/sirix
aledalgrande 7y ago
Love these kind of problems... is chunking the same as streaming in this context?
jniedrauer 7y ago
Go makes solving problems like this an absolute joy. I recently ran into a situation where I had to download and extract a very large tar archive, then send its contents to another network resource. The device doing the extraction had severely restricted memory and storage space. Since gzipped tar archives contain sequential data, solving it ended up being trivial. With Go, I was able to string together the file download, tar extraction, and forwarding the individual files on, all within the context of a single stream.
- kccqzy 7y ago
  How is that better than curl ... | tar xv | ... in shell, or any programming language with a good streaming library?
  - jniedrauer 7y ago
    It's not. It's not a novel concept. But it's very clean, readable code in Go.
adrianmonk 7y ago
Also look at whether you can solve your problem with a different algorithm, one that is more friendly to external storage. One classic example is sorting. When your data is too big for RAM, quicksort's performance is horrible and mergesort's performance is fine (even if your data is on magnetic tape). Another classic example is taking a situation where you build a hash (or dictionary) and using sorted lists instead. Let's say your task is to take some text and put <b></b> tags around a word but only the first time it occurs. The obvious solution is to scan through the text, building a hash as you encounter words so you can check if you've seen it before. Great until your hash doesn't fit in RAM. The sort-based solution is to scan through the input file, break it into words, and output { word, byte_offset } tuples into a file. Then sort that file by word using a stable sort (or both fields as sort key). Now that all occurrences of each word are grouped together, make a pass through the sorted data and flag the first occurrence of each word, generating { byte_offset, word, is_first_occurrence } tuples. Then sort that by byte_offset. Finally you can make another pass through your input text and basically merge it with your sorted temp file, and check the is_first_occurrence flags. All of this uses O(1) RAM. I believe this is basically what databases do with merge joins, but the point is you can apply this general type of thinking to your own programs as well.
- gspetr 7y ago
  I believe this is a problem that CS has already solved: http://dimacs.rutgers.edu/~graham/pubs/papers/cmsoft.pdf http://dimacs.rutgers.edu/~graham/pubs/papers/cmsoft.pdf The Count-Min Sketch is a data structure consisting of a fixed array of counters. This is a short and easily accessible paper, which isn't very heavy on math or obscure notation or concepts, so I would recommend it to anyone with even a cursory interest in the subject. Here's an implementation in Python: https://github.com/barrust/count-min-sketch/blob/master/python/countminsketch.py https://github.com/barrust/count-min-sketch/blob/master/pyth...
movieswebsite 7y ago
very nice https://superfastblog1.blogspot.com/2019/11/best-free-photo-editor-online.html https://superfastblog1.blogspot.com/2019/11/best-free-photo-...
bmer 7y ago
I am surprised there is no mention of hdf5 (via h5py). It's what I used to deal with handling simulation data that was getting too big for RAM to handle. Use case: CPU is running a simulation and constantly spitting out data, eventually RAM is not enough to hold said data. Solution: every N simulation steps, store data in RAM onto disk, and then continue simulating. N must be chosen judicially so as to balance time cost of writing to disk (don't want to do it too often). I figure this is what is referred to as "chunking" in the article? Why not list some packages that can help one chunk? Overall opinions on this method? Could it be done better?
- CreRecombinase 7y ago
  This is exactly what HDF5 was built for. Figuring out how often to persist to disk is going to depend on a number of factors. If you want to get fancy you can dedicate a thread to I/O but that gets hairy quickly. You also might want to look into fast compression filters like blosc/lzf as a way of spending down some of your surplus CPU budget.
- JBorrow 7y ago
  That depends - we use HDF5 to store data from huge simulations (~1TB/snap) which are then obviously too large to analyse on a single machine. The benefit of HDF5 is that it allows for very easy slicing of data. So 'chunking' where I load e.g. 10% of one dataset at once is very simple with HDF5.
miles_matthias 7y ago
Just want to compliment how well written this article is. A lot of technical articles lack the context or basic background (“why”) and this article does a great job.
- SlowRobotAhead 7y ago
  Why / Intent is the biggest overlooked aspect of computer science / computer engineering imo. I just wish more technical documentation had a human element of “what we intended” to it.
dschuetz 7y ago
Did I miss something? Why would anyone open and load a 100G file all at once on a 16G machine? Why is there such a file in the first place?
jacquesm 7y ago
I'm missing the most obvious one: check to see if you need all that data. Plenty of times you can get 98% of the quality with a small fraction of the available data. Doing a couple of tests to determine what constitutes a representative sample could save you a ton of time and a ton of money.
- ImaCake 7y ago
  I spent a few weeks on-and-off between more important study, trying to help a friend process their sequencing data in a bespoke way. I kept trying to write an algorithm that would take about 500 hours to run. I first used Pandas (which is kinda slow) and then tried base python dict() and iterables. Eventually I realised that most of the data was actually redundant if I just counted how many instances of each unique row were in my dataset and then just threw away the extras while keeping the counts for later. My new algorithm did what I wanted in 8 seconds flat and was only a tiny bit more effort to integrate with the counts. My lesson learnt was that I just needed to reduce how much data I was working with first, instead of trying to stuff a multi-gb file into memory!
- blablablerg 7y ago
  This is the number one thing to check first.
nik_ma 7y ago
Nice article
novaRom 7y ago
There is no simple solution because any compression/decompression costs you computations. If data is stored uncompressed, it takes more space but access takes less time than if the data were stored compressed.
ak39 7y ago
When your data doesn't fit in memory: SQLite
- lytefm 7y ago
  Yeah for me this was also the obvious solution when I had to extract information from ~80 GB of tabular data. It's not the most trendy tool, but it did the job extremely well and with little effort. Just be sure to only create an index after having inserted all the data...
  - ak39 7y ago
    Correct. Drop indexes for inserts and recreate after bulk inserts. Also, another hint: process all inserts in the bulk in a single transaction. I was amazed at the speed that SQLite ingests data! Speed demon! (Don’t forget PRAGMA synchronous OFF too)
drej 7y ago
One can efficiently stream data even when there's a need to combine multiple streams. I oftentimes have data sorted on its ID, for instance (usually when it comes from a database), and then can easily join and group by this ID (the same way `uniq` would). All using Python's standard library, here's a quick post I wrote about this. I last used it a week ago and got from 950 MB RAM usage down to about 45 megs. https://kokes.github.io/blog/2018/11/25/merging-streams-python.html https://kokes.github.io/blog/2018/11/25/merging-streams-pyth...
alanbernstein 7y ago
Want to compress and index your data at the same time? Use roaring bitmaps! A bitmap representation of data is surprisingly flexible for computation, and roaring uses some clever tricks to do that with high performance. For additional scalability, try pilosa, a distributed database built on top of roaring (I work for the company that maintains pilosa). https://roaringbitmap.org/ https://roaringbitmap.org/ https://www.pilosa.com/ https://www.pilosa.com/
alexcnwy 7y ago
There's a lot of room between a laptop with 16GB of RAM and a "Big Data cluster" - in my experience the easiest solution is to spin up a VM in GCP and crank the RAM way up. It blew my mind when I realized I could add / remove RAM by turning off the instance, dragging a slider, then turning it back on. I also find h5py really useful for creating massive numpy arrays on disk that are too large to fit in memory. I used it to precompute CNN features for a video classification model (much faster than computing on each gradient descent pass) and it makes it easy to read/write parts of a numpy array when the entire numpy array is too big to fit in memory.
- stilley2 7y ago
  Besides compression, is there an advantage to using h5py over numpy's memmap?
rmuchev 7y ago
If your data needs sorting and does not fit in memory: https://github.com/rmuchev/ExternalSort https://github.com/rmuchev/ExternalSort
snvzz 7y ago
Odd not to see any reference to mmap, which is part of the python library.
RocketSyntax 7y ago
step 1. use a generator instead of a loop https://realpython.com/introduction-to-python-generators/ https://realpython.com/introduction-to-python-generators/
drderidder 7y ago
Somebody needs to tell this guy about a thing called a "database".

638 points by itamarst 7y ago

Unusual to have no occurrence of the word "stream" anywhere in the article... given that's the usual term for algorithms which require a constant or almost-constant space regardless of the amount of data they process. A semi-common beginning programmer's exercise is to write a program that numbers the lines in a text file. The naive solution will use O(n) space, while a bit more thought reveals that this can be done in constant (to be really precise, O(log n) where n is the number of lines in the file) space.

itamarst 7y ago
Chunking is the term I used because that's more relevant to the data science domain I'm focusing on here (e.g. Pandas has "chunksize", Zarr has "chunks"). Streaming has some implication of an ongoing stream of data to me... but I ought to clarify some of the assumptions about a fixed size of data, yes.
- denhaus 7y ago
  Ditto. Python multiprocessing also uses “chunks” with a specified chunksize.
- roter 7y ago
  netCDF, used for storing e.g. large multidimensional climate datasets, is also "chunked" through its HDF[0] backbone. The hard part for me is the "transpose" or "striding" problem. i.e. when the data is stored in a series of (x, y, z) files for a given hour, day, or month and I need a time series at a point. [0] https://en.wikipedia.org/wiki/Hierarchical_Data_Format https://en.wikipedia.org/wiki/Hierarchical_Data_Format
- dmurray 7y ago
  Chunking and streaming are different things to me. Chunking means you get to process multiple rows of data at the same time, usually useful to take advantage of SIMD. Streaming means that the data is accessed in a single pass: once you compute the effect of a given row on your statistics, you never have to rewind to see it again. Many modern performant solutions will use both, but they're not the same thing.
  - nine_k 7y ago
    One important application of chunking is efficient I/O. Mass storage is most efficient when doing large sequential reads and writes, so you normally feed your constant-space streaming algorithms from buffers with a large number of input records. Sometimes you can just tell the OS do efficient chunking prefetch for you.
    - hofstee 7y ago
      If you're streaming in a language like Python, its IO will be doing some degree of chunking behind the scenes. It might be beneficial to do more manually.
    - Sean1708 7y ago
      Often called buffering when applied to IO.
- pythonwutang 7y ago
  > Chunking is the term I used because that's more relevant to the data science If your intended audience are data scientists then why didn’t you mention Dask?
mytailorisrich 7y ago
> A semi-common beginning programmer's exercise is to write a program that numbers the lines in a text file. In term of RAM this can be done an arbitrarily small buffer in the sense that this can be done by reading the file byte by byte. I.e. O(1). Edit: For all practical purposes the line counter is also constant space.
- rongenre 7y ago
  Yeah log(n) would be the space to hold the digits of the counter. Presumably (unless things got super-silly), this would be dominated by the buffer size for the line being read.
  - dfox 7y ago
    The point there is that you don’t need a buffer for whole line, you only have to find the line terminators. Something like: printf(“0: “); ln = 1; while ((ch = getch()) != EOF) { putch(ch); if (ch == EOL) { printf(“%d: “, ln); ln++; } } And I believe that original unix implementation of nl is mostly this, although with the stdio functions replaced with raw read/write.
- johnc1231 7y ago
  Yeah, I think the above poster said O(logn) space because that's the size of the line count in bits
  - jeremysalwen 7y ago
    The usual computation model includes "log n sized words", so it really is O (1). You usually are implicitly using that model, otherwise any algorithm that used pointers would have an extra log n tacked on, e.g. linked lists append would be log n not constant.
gwbas1c 7y ago
> Unusual to have no occurrence of the word "stream" anywhere in the article... Or "database"
- nautilus12 7y ago
  Both indicators (along with python) that this is an article written by a yet another data scientist that thinks engineering is unecessary. Data science is a field that is plagued by individuals having very specific narrow experiences that are often easy to engineer making them think they are experts in data engineering. Vertical scalability has a hard bound, if your algorithm changes complexity it could become literally impossible to move forward. Horizontal scalability gives you options, this is why we like it, not just because we like to overengineer systems, but because we don't like embracing hard limitations on the systems we engineer, especially when we often don't know yet what problem we are solving. Engineers often don't get the liberty of solving extremely specific instances of problems like data scientists do.
  - realusername 7y ago
    > Data science is a field that is plagued by individuals having very specific narrow experiences that are often easy to engineer making them think they are experts in data engineering. That's on point, some of the worst and most inefficient code I had to maintain was written by data scientists. They are for sure leagues above any of my data science knowledge in their respective field but the average engineering knowledge and best practices seems pretty low.
  - deleted 7y ago
    [deleted]
  - kyllo 7y ago
    Most of the time it's not that data scientists think engineering is "unnecessary," it's that they're expected to deliver analyses and models without the help of engineers, because the engineers are on another team, behind a massive backlog. So they make do with the tools they have.
rhinoceraptor 7y ago
> write a program that numbers the lines in a text file Ah, simple :) cat file | wc -l
- dyanaraps 7y ago
  Useless use of `cat`. :) wc -l file To hide filename: wc -l < file
  - scarejunba 7y ago
    I'm actually pretty much against UUoC. The cat example is much more resilient to modification. For instance, there are usually natural modifications considering filtering etc. Anyway, since he said number we probably want `nl` not `wc`. Separating pipe-setup from processing is sound engineering to me and makes things much easier. For instance as I iterate, I will have cat piped to head piped to filter but eventually I'll take the head out and run the whole thing. That's a trivial ^W versus moving around arguments and worrying about arg order, etc.
    - navaati 7y ago
      That's right regarding directly giving the filename for the program (here wc) to open itself. However using the input redirect is fine, especially if you format it that way (which is exactly the same thing): <file wc -l Then, adding another step is as natural as with cat: <file grep meh |wc -l
      - thestoicattack 7y ago
        Useless use of `wc` :) <file grep -c meh
        deleted 7y ago
        [deleted]
      - herpderperator 7y ago
diabeetusman 7y ago
Sorry, isn't there quite a bit of a difference between O(1) and O(log N) space? My first inclination would be to have a counter at zero, read in a line, write out the counter then write out the line, then increment the counter. The space complexity here is O(1), is it not?
- yifanl 7y ago
  Storing the number n takes log n bits, if we're being super pedantic :)
  - thfuran 7y ago
    In practice, I'd say it takes exactly 64 bits for any file.
    - MiroF 7y ago
      Asymptotic notation isn't about what's "in practice." We have very good asymptotic complexity for multiplication, but don't use the ones that scale the closest to linear because the time constant is enormous.
      - dfox 7y ago
        With the O() notation the units are some arbitrary computation step or arbitrary unit of memory, which could even mean matrix multiplication of two 1024x1024 matrices of doubles. The whole point of big-O notation is that you don’t care about how fast/expensive it is, but how it scales.
        MiroF 7y ago
        Yes and the memory to store a number scales with the log of the number
      - darkmighty 7y ago
        There are different models of computation. You can have a model in which integers can be arbitrarily large yet still count as constant memory (for analyzing practical-size algorithms on 64-bit machines, for example); I'm not sure how common those are. I know for example arithmetic is often assumed to be constant time (it indeed varies by input size, even x=y+1, which is clearly O(log(y))). Also relevant here is the RAM machine model that is often employed, where you can have essentially unlimited memory that can be randomly accessed at fixed time. This again is roughly in line with real practical machines running algorithms that use, and fit within RAM. In reality if you wanted a more physically consistent model eventually your access times must differentiate and increase for increasing memory -- data occupies physical space and must be fetched at increasingly long distances, limited by the speed of light. In principle this means m bits of memory at best can be accessed in O(m^(1/3)) time [1]. Of course, this realism isn't always practically relevant (maybe for datacenter-scale problems, perhaps even larger) and complicates the analysis of algorithms. [1]: Just for fun, if you want to get really physically accurate, this isn't quite right either I suspect -- that's because with enough data (physical bits) occupying a volume at constant density it will eventually collapse into a black hole, which kinda destroys your computer :). So for planetary-scale computers you eventually need to spread your data across a disk, like a small galaxy (or Discworld, if you prefer :)), so it won't collapse, giving it O(sqrt(m)) access time. Surprise, very large worlds must be flat. This is related to the BH entropy formula, and the so called Holographic principle, I guess -- the entropy and hence information content of a volume is surprisingly bounded by its area, since a Black Hole's area is proportional to its mass. The weird thing of course is how the universe itself perhaps should collapse to a black hole since it has a lot of stuff in any sufficiently large volume, being young and dynamic it hasn't happened yet. It's alsogiven by its fractal scale, but I guess this digression has grown large enough already :) (do tell if you want to learn more)
tehsauce 7y ago
O(log n) is not constant
- mark-r 7y ago
  I think the point in this case is that log n has a reasonable upper bound, and can be considered constant for any real world problem.
WanderPanda 7y ago
O(log n) is so precise it ain't even informative :P
bogomipz 7y ago
>The naive solution will use O(n) space, while a bit more thought reveals that this can be done in constant (to be really precise, O(log n) where n is the number of lines in the file) space" Can you elaborate on the O(1) solution?
- xondono 7y ago
  Not an expert, but after reading around OP is saying you only need a constant sized buffer (that could be as little as a character deep) to read the whole file looking for line breaks. This roughly takes O(1) space (A lot of commenters are confusing time vs space requirements) but there's a little nitpick to be found, in extremely big files the line counter itself would be O(log(n)) and would dominate.
  - bogomipz 7y ago
    I see, yes that makes sense. The conflation with time instead of space was confusing me. Thanks.
tmh88j 7y ago
>A semi-common beginning programmer's exercise is to write a program that numbers the lines in a text file. The naive solution will use O(n) space, while a bit more thought reveals that this can be done in constant (to be really precise, O(log n) where n is the number of lines in the file) space. I guess I'm misinterpreting the task, because I'm having trouble seeing how it's possible to access each line in a file without it being O(n) at a minimum. I understand O(log n) to mean that not every data point is "accessed" due to the way the data structure is organized, lines of a file in this case, but to me it appears that not every line would be prepended with a number. My instinct is that there's a lot going on with new lines/line breaks in files that I'm not aware of, so I'd really appreciate any reading material on the subject to help me better understand this. Thanks!
- unlivingthing 7y ago
  I think you've got confused with O(n) time; that is the amount of memory that is needed and not the time required to access a particular line.
  - tmh88j 7y ago
    Good point, I was thinking in terms of time complexity rather than space, but the title clearly is in reference to memory. I guess that explains my confusion!
  - profmonocle 7y ago
    I made the same mistake at first, had to reread the post. I'm so used to seeing Big O notation used for time that I guess my eyes just passed over the word "space". (My mistake obviously, the OP was very clear.)
3xblah 7y ago
sed = 1.txt Use small buffer. No need to fit all the data into memory.
kashif 7y ago
I was also surprised by the lack of streaming. In Python specifically for really large JSON datasets I wrote this streamer that many have found useful - https://github.com/kashifrazzaqui/json-streamer https://github.com/kashifrazzaqui/json-streamer
deleted 7y ago
[deleted]

Sahonon 7y ago

Dumb question, but wouldn't memory mapping or lazy/streaming processing (e.g. SAX for parsing large XML documents, Java Streams for handling large amounts of "things", memory mapped files for anything you don't need intermediate representations for) resolve this problem as well?

itamarst 7y ago
See above about streaming (chunking is basically the same thing). mmaping is a form of uncontrolled chunking, where chunk size and location is determined by operating system's filesytem caching policy, readahead heuristics, and the like. As a result, it can sometimes have much worse performance than an explicit chunking strategy, especially if you just treat it as magic. Or to put it another way, mmaping is helpful but you still need to understand why it might help and how to use it.
- faizshah 7y ago
  > it can sometimes have much worse performance than an explicit chunking strategy Can you expand on this? I haven’t heard this before. Edit: Found a comprehensive discussion on this https://stackoverflow.com/questions/45972/mmap-vs-reading-blocks https://stackoverflow.com/questions/45972/mmap-vs-reading-bl...

amoron 7y ago

I would just cat | grep | awk | sed on this stuff rather than resorting to Py.

j88439h84 7y ago
Awk pipelines are exactly the area where Mario is useful for Python programmers. https://github.com/python-mario/mario https://github.com/python-mario/mario

wongarsu 7y ago

Another key technique I've used is to use pipes and basic command line tools where possible to pre- or postprocess your data. For example a `sort | uniq -c | sort -nr | head` pipeline to get only the most frequently occurring lines works in a few kilobytes of ram no matter how big the input is. Combine this with chunking and you can get a lot of data processed in manageable amounts of memory. Of course the next problem is "my data doesn't fit on disk", but with xzcat on the command line and lzma.open in python you can work transparently with compressed files.

vardump 7y ago
> Of course the next problem is "my data doesn't fit on disk", but with xzcat on the command line and lzma.open in python you can work transparently with compressed files. I usually use LZ4 compression for this purpose, because it's ridiculously fast (700 MB/s per core compression and 5 GB/s decompression). Sure, compression ratios aren't as good, but usually good enough.
muxator 7y ago
Completely agree (I do this myself all the time) but keeo in mind the initial sort has not a constant cost in term of memory. Yet, one realizes how well written these basic tools are only after having some bruises with fancier tools.
- wongarsu 7y ago
  I don't know what POSIX says on the matter, but at least GNU sort uses some variation of merge sort with temporary files and has for all intents and purposes constant memory use.
naniwaduni 7y ago
Compression alleviates the problems "my current disks don't fit my data" and "my data is too big for my disk quota". It's comparatively bad at solving the problem "I cannot buy enough disks to fit my data".
namibj 7y ago
zstd is nearly always superior to xz, fyi.

RcouF1uZ4gsC 7y ago

> The easiest solution to not having enough RAM is to throw money at the problem. People underestimate how much memory modern computers can actually support if you max them out. http://www.itu.dk/people/jovt/fitinram/ http://www.itu.dk/people/jovt/fitinram/

wongarsu 7y ago
And not just on super fancy computers, 128GB of RAM is like $500 and is supported by many low-to-mid-range desktop systems.
- kevin_thibedeau 7y ago
  Without ECC that's a risky way to compute.
  - ben-schaaf 7y ago
    IIRC ryzen in general can run with ecc, though motherboard support is a little shaky
  - wongarsu 7y ago
    Eyeballing the numbers [0][1] I would expect one bitflip between once every year and once every 100 years on 128GB of memory. I'm willing to take those odds. Of course with some planning you can get an AMD system with ECC support on the mainboard; ECC RAM is about the same price as consumer RAM. 0: https://www.cs.toronto.edu/~bianca/papers/sigmetrics09.pdf https://www.cs.toronto.edu/~bianca/papers/sigmetrics09.pdf 1: https://www.cs.virginia.edu/~gurumurthi/papers/asplos15.pdf https://www.cs.virginia.edu/~gurumurthi/papers/asplos15.pdf
    - nostrademons 7y ago
      When Craig Silverstein left Google somebody asked him "What was the biggest mistake you made while at Google?" His response was "Not using ECC memory." The problem is that both the consequences and debugging time of a single random bitflip are potentially unbounded. That time that GMail lost 10% of their accounts and had to restore from tape was because of a single bitflip (due to a software bug, not a cosmic ray). Google Search lost months of engineering time in the early days from cosmic rays, back when they really could've used those engineers on other stuff. The odds may be low, but they do happen when you have multiple computers, and the consequences are high. Not really odds I'd want to take, when ECC RAM isn't that much more expensive than non-ECC RAM.

threeseed 7y ago

You can spin up a standalone Spark cluster in about an hour and it's pretty easy. And yes you will need to rewrite a small amount of your code but you're doing so here as well. At least you will be able to scale out to much larger volumes in a consistent way.

zaphar 7y ago
For many tasks a spark cluster is overkill. Streaming will get you a really long way before you have to tackle running a while spark cluster. And you'll probably be able to still do it on your laptop.
- threeseed 7y ago
  You can't just apply a streaming paradigm to a batch style workload. And 90% of all tasks are batch orientated.
  - zaphar 7y ago
    Batch is just streaming in really large chunks. And besides if you are messing around with data on your laptop you probably aren't at the stage of working out a batch workload yet. Jumping immediately to this needs to be a batch workload before you have had a chance to play with it is probably overkill.

cosmic_quanta 7y ago

I wrote a library to deal with this problem when it comes to NumPy arrays (e.g. images). Could not fit all images in RAM, so I went with a constant-memory approach[0]. The reduction in memory has allowed us to do parallel processing, for a pretty significant speed-up! [0](github.com/LaurentRDC/npstreams)

gwbas1c 7y ago

> When your data doesn’t fit in memory: the basic techniques Uhm... Isn't it called a database? Jokes aside, one of the core use cases of things like databases is random access to a part of data that's too large to fit in RAM.

dev_dull 7y ago
My assumption was that the system had finite ram available, whether that's serialized in a database or read directly into the program.
- gwbas1c 7y ago
  So? Typically "database" implies a product like SQLite or Postgres. These handle many multiples of RAM size. In-memory databases are a thing, but that's a very specialized use case.
  - dfox 7y ago
    Somewhat surprising fact about most PostgreSQL deployments is that most of the frequently accessed tuples will fit into RAM and it handles this usecase really well (to the extent that people who don’t know any better do not see any issue with LIKE ‘%whatewer%’ over 100M tuple table, it just takes 1.5s, so what...)
- PhearTheCeal 7y ago
  Pretty much all SQL DBs support pagination, and many libraries that abstract the DB away hide this as an iterator.
VikingCoder 7y ago
Hi, once upon a time, I worked with medical image data. I literally had a DBA suggest storing the volumetric data in a database. I worked to diligently to explain to him why he was incorrect. When he resisted my explanations and tried to push forward with his plan, I worked diligently to get him fired. I was successful.

xiaodai 7y ago

Use Dask. In R for tabular data use disk.frame

floki999 7y ago

Dask anyone? Allowed me to handle a 60 Gb dataset on a machine with 16 Gb RAM. High level of compatibility with Pandas dataframes.

xiaodai 7y ago
I mean, don't reach for Spark. Just get Dask, a databased or R's disk.frame is mostly fine.
roaur 7y ago
I'm a Dask evangelist. It's a remarkable tool and is one of the first I reach for when this problem arises. Maybe it's not well known?

wooly_bully 7y ago

The "spin up a big data cluster" bit at the beginning seems like either a straw man or just oddly out of touch. Who, when determining how to process something on the order of a 100gb file, even considered something like that? Also, SQLite is a first class citizen in this space. Most if not all languages can easily load data to it, virtually any language used for analysis can easily read from it, and it's file-based so there's no reason to spin up a server. Finding 100GB on disk is much easier than 100GB in ram.

mumblemumble 7y ago
Divide that file size by 10, and you're still in the range where I've had to argue that rolling out Spark is overkill.
- zetazzed 7y ago
  People will disbelieve that, but it's absolutely true... I'll never forget the interview I did with an engineer who described an elaborate Hadoop-based solution to some past problem. When I asked him what type of data he was working with, he said, "Here, I'll show you," then whipped out his laptop and showed me a spreadsheet. It wasn't an extract of the data. It was literally a spreadsheet, manageable on a laptop, that he somehow decided needed a Hadoop cluster to process. (Also, who shows data from your current employer to a new prospective employer? Weird but true.)
  - mumblemumble 7y ago
    I had an interesting experience a while back where it came to light that I was working on the same problem as another team in the org (this was a huge multinational), so a meeting was arranged so we could compare notes. The other team was slightly shocked to see that I could train a model in a minute or two, where it took them an hour or two using essentially the same algorithm. They insisted that shouldn't be, because I was doing it on my laptop and they were using a high performance computing cluster. They of course wanted to know how my implementation could be so much faster despite running on only a single machine. I didn't have the heart to suggest that maybe it was because, not despite. Ironically, I also got the implementation done in a lot fewer person-hours. I just did a straight code-up of the algorithm in the paper, where they had to do a bunch of extra work to figure out how to adapt it to scale-out. This isn't to say that big data doesn't happen. Just that it's a bit like sex in high school: People talk about it a lot more than they actually have it, perhaps because everyone's afraid their friends will find out they don't have it.

zneveu 7y ago

Another easy solution I didn't see mentioned is to create swap space on Linux. This obviously isn't the fastest solution, but setting up 128GB of swap space let's me mindlessly load most datasets into memory without a single code change.

yummypaint 7y ago
Do you have a sense of how the performance would compare to chunking? My naive expectation is that loading data from disk to swapped memory involves writing that data to disk (even if it will only be read).
- wongarsu 7y ago
  Chunking can speed up processing even if the dataset fits into memory because you are interleaving disk reads and computation and the OS is likely to prefetch the next chunk into the read cache while you're still busy computing. On other problems chunking doesn't work at all and just mmaping or dedicating giant amounts of swap are better strategies. It depends on the problem at hand
olavgg 7y ago
Adding a 280GB Optane as swap is very efficient and cheap. It is still a lot slower than RAM though. But much much faster than NVME ssd's
- p1esk 7y ago
  Are you talking about Optane NVDIMM or NVME?
Rafuino 7y ago
Plus, swap performance is being improved bit by bit, so it's not as much of a dirty word as it was before. https://lwn.net/Articles/717707/ https://lwn.net/Articles/717707/
oxplot 7y ago
This! It's simple, performant depending on application and costs zero in extra development.

__sy__ 7y ago

Just wanted to chime in to say that the Tensorflow 2.0 Dataset Library is nice for this sort of problem. It supports batching, caching, remote fetching, multiple cpu core splitting...etc.

onikolas7 7y ago

Fun fact for non CS people, which this article seems to address. Nothing fits: disk to RAM, RAM to L3, L3 to L2, L2 to L1, L1 to registers. We are just lucky that many programs have spatial and temporal locality.

bufferoverflow 7y ago
It looks like disk and RAM will merge soon into some form of insanely fast and persistent storage. And L3 is already at 256MB (+32MB L2) in the new AMD Threadripper CPUs.

daveslash 7y ago

The article mentsions Rent a VM in the cloud, with 64 cores and 432GB RAM, for $3.62/hour.. Does anyone have specific services they'd recommend?

Aperocky 7y ago
Plenty of options in the price range/ spec range for AWS: https://aws.amazon.com/ec2/pricing/on-demand/ https://aws.amazon.com/ec2/pricing/on-demand/ If you sign up by month it will be much cheaper too.
kathrynloving 7y ago
I'm working on a new platform to easily deploy compute/memory-intensive applications to cloud API endpoints [1]. This let's you share your app with others (e.g. colleagues) and makes the most sense if your task needs a lot of memory/CPU but not too much IO. Contact info is in my profile and I'm happy to discuss your use case! [1] https://www https://www explorablelabs.com
- pojzon 7y ago
  You mean like terraform using predefined ami >_>?

scottlocklin 7y ago

^f mmap yeah, that's what I thought.

eggie5 7y ago

one word: Dask

elchief 7y ago

Ah yes. A problem they solved 50 years ago

hinkley 7y ago
We are about 5 years out from that being true for pretty much everything. Most of the problems we fight over were identified by the early 70's.

anotherevan 7y ago

The nice thing about virtual memory is you can make really big RAM disks…

gowld 7y ago
Isn't that a regular disk, with your OS's (or SSHD's) file cache?
- mbreese 7y ago
  No, in this context, it's creating a virtual disk using only RAM as a backing store. If you do this, then you can use whatever tools you'd normally use (cat, wc, grep, etc) to explore a dataset as if they were files. It's the super quick and dirty way to go if you don't want to code up a proper solution and your data fits in RAM. (assuming the data is organized in files to begin with)

hamsham 7y ago

I recently ran into an issue in a game where my team and I were storing hundreds of 160-byte config structures in memory. It blew up to over 86kb of data (which doesn't seem like much, but we're already pressed for memory at a 64mb-limit). I compressed the configs by packing the structure into a 2-byte bitfield, simply twiddling bits to get/set each parameter, and just like that the 86 kilobyte configs dropped to just over 1kb. We're still trying to reduce memory elsewhere but the savings showed we can do similar tricks to significantly save our memory footprint in other places.

baybal2 7y ago

I think the author completely misses a mention that sequential access to cold store is nowhere as slow as access to ram. Cold store looses big in only scenarios where you have sequential and completely random seek patterns, and there are lots of way to optimise that in read and write heavy workloads. This was the art of running performant multi-terabyte DBs in a world prior to SSDs and ramdisks. For very big index walks, you want to have data to be more flat, and seeks to be sorted, so there is higher chance that needed records would be accessed without page eviction. Modern DBs, I believe, do something like that internally. And for write heavy loads, there is no alternative to revising "data structures 101." You can reduce the disk load by may times over with a properly picked tree, graph, or log structure.

lichtenberger 7y ago
Just wanted to add that tree and graph structures of course can be stored sequentially on disk or a flash drive (log-structured). For instance with a really fast random access storage and some additional space you can even save the history, that is lightweight snapshots of your data. That is you always append data. This way you can also use clever versioning algorithms to predict the performance (no read or write peaks) and to lower the space consumption.
vikiomega9 7y ago
Do you a list of required reading?

cpa 7y ago

A few years ago, I found surprisingly difficult to sort a file that didn't fit in RAM in Python; I couldn't find any simple libraries for this kind of stuff. Disappointingly, I ended up writing my data to a text file, sorting with unix sort (w/ some tuning on --parallel and --buffer-size) and reading it back.

madhadron 7y ago
> Disappointingly, I ended up writing my data to a text file, sorting with unix sort (w/ some tuning on --parallel and --buffer-size) and reading it back. One of my biggest beefs with Unix is that so much powerful functionality is locked up in command line utilities and not accessible as libraries.

longemen3000 7y ago

Im following closely the development on an alternative to data.frame that works on disk (disk.frame),using the same API

lllr_finger 7y ago

Binary serialization and real-time compression like zstd have opened up a whole new world for me. Something like flatbuffer even lets you index into structured data without a deserialization penalty.

SlowRobotAhead 7y ago
I’m also a fan of serialization that allows for streaming and in-memory access without fully deserializing. The project I’m working on uses CBOR and it’s been working really well. Not using the streaming, but being able to quickly access without transforming the data has been huge.

lmilcin 7y ago

mmap() anyone? Seriously, this should be the top of the list and default solution when you need to process large file that does not fit in memory. The exceptions would be when you can read the file once (then stream might be easier but not cheaper), when you don't want to rely on FS cage (you need your own) or when you need easy interoperability between different OS-es.

jdmoreira 7y ago
I came to the comments after reading the article just to find the person suggesting mmap and upvote them :)
- neop1x 7y ago
  Exactly! Me too :D
  - lmilcin 7y ago
    It is quite saddening for me that so few developers try to take advantage of the tools available. It is really magical thing to be able to run just a single function and have your entire terabyte file suddenly present itself as addressable continuous memory space ripe for random access. Regular random access file I/O seems silly to me, like trying to work with the file through a key hole. Have you ever seen how ships are built inside a bottle? That's exactly the picture I have in my mind...

beached_whale 7y ago

mmap can really help with this too. It won't stop you from being silly and using random memory access patterns, but it does abstract away the file access as a piece of address space. Short of running on a 32bit machine, this can help a lot. Even on a 32bit machine you can abstract it away with another later and window the access.

gowld 7y ago

Not perl? I'm compelled to respond with "OK Boomer".

blueyes 7y ago

Since this is an article about speed and data processing on a Python blog, I'll just point out that the RiseLab team that created Ray and RLlib also has a library called Modin, which is distributed Pandas. You just import modin as pd without changing the code: https://github.com/modin-project/modin https://github.com/modin-project/modin

jszymborski 7y ago
and in that vein, Dask: https://dask.org/ https://dask.org/
marcinzm 7y ago
It will, however, from my reading convert the data to an actual pandas dataframe for certain operations. Which presumably is bad if your data doesn't fit into memory.

opdahl 7y ago

I'm currently running an index that requires over 64GB of ram. There's no possibility of lowering this, but I don't have a really high requirement for latency. So my solution was to get an M2 storage instance and create a 100GB swap space. Works like a charm and in the future, if I need the higher latency I just change the instance to something that has enough ram.

emmelaich 7y ago

There's an enormous amount of literature and technique in the mainframe world for dealing with data bigger than ram. Because that was the norm. Whole companies have been built around the problem. e.g. syncsort.com I hope some interesting techniques don't get locked up and lost in proprietry mainframe software.

cozzyd 7y ago

Here's where ROOT really shines

RivieraKid 7y ago

Another one: reservoir sampling. It's used in Deep CFR, a form of CFR that uses neural networks. CFR is an algorithm used for finding equilibrium strategies in imperfect information games, most notably poker. https://en.wikipedia.org/wiki/Reservoir_sampling https://en.wikipedia.org/wiki/Reservoir_sampling

lichtenberger 7y ago

I'm working on storing data in a log-structure persistently without the overhead of a transaction log in my spare time (Open Source[1]). Instead, an UberPage which guarantees consistency is atomically swapped during a transaction commit (inspired by ZFS). It should be used for data, which doesn't fit into main memory. Revisions are always appended, whereas almost only changed data plus some metadata is written to a file during commits. You can easily retain the full version history in a log structure, but you need fast random access (option of parallel "real" access would be best) on a flash drive -- PCIe SSDs for instance. Basically in order to balance read and write performance only a fraction of each database page (with changed records) needs to be written sequentially in batches to the end of a file. Each revision is indexed under a RevisionRootPage and these are indexed under the UberPage with keyed tries. This opens up a lot of opportunities for analysing data and its history. [1] https://github.com/sirixdb/sirix https://github.com/sirixdb/sirix

aledalgrande 7y ago

Love these kind of problems... is chunking the same as streaming in this context?

jniedrauer 7y ago

Go makes solving problems like this an absolute joy. I recently ran into a situation where I had to download and extract a very large tar archive, then send its contents to another network resource. The device doing the extraction had severely restricted memory and storage space. Since gzipped tar archives contain sequential data, solving it ended up being trivial. With Go, I was able to string together the file download, tar extraction, and forwarding the individual files on, all within the context of a single stream.

kccqzy 7y ago
How is that better than curl ... | tar xv | ... in shell, or any programming language with a good streaming library?
- jniedrauer 7y ago
  It's not. It's not a novel concept. But it's very clean, readable code in Go.

adrianmonk 7y ago

Also look at whether you can solve your problem with a different algorithm, one that is more friendly to external storage. One classic example is sorting. When your data is too big for RAM, quicksort's performance is horrible and mergesort's performance is fine (even if your data is on magnetic tape). Another classic example is taking a situation where you build a hash (or dictionary) and using sorted lists instead. Let's say your task is to take some text and put <b></b> tags around a word but only the first time it occurs. The obvious solution is to scan through the text, building a hash as you encounter words so you can check if you've seen it before. Great until your hash doesn't fit in RAM. The sort-based solution is to scan through the input file, break it into words, and output { word, byte_offset } tuples into a file. Then sort that file by word using a stable sort (or both fields as sort key). Now that all occurrences of each word are grouped together, make a pass through the sorted data and flag the first occurrence of each word, generating { byte_offset, word, is_first_occurrence } tuples. Then sort that by byte_offset. Finally you can make another pass through your input text and basically merge it with your sorted temp file, and check the is_first_occurrence flags. All of this uses O(1) RAM. I believe this is basically what databases do with merge joins, but the point is you can apply this general type of thinking to your own programs as well.

gspetr 7y ago
I believe this is a problem that CS has already solved: http://dimacs.rutgers.edu/~graham/pubs/papers/cmsoft.pdf http://dimacs.rutgers.edu/~graham/pubs/papers/cmsoft.pdf The Count-Min Sketch is a data structure consisting of a fixed array of counters. This is a short and easily accessible paper, which isn't very heavy on math or obscure notation or concepts, so I would recommend it to anyone with even a cursory interest in the subject. Here's an implementation in Python: https://github.com/barrust/count-min-sketch/blob/master/python/countminsketch.py https://github.com/barrust/count-min-sketch/blob/master/pyth...

movieswebsite 7y ago

very nice https://superfastblog1.blogspot.com/2019/11/best-free-photo-editor-online.html https://superfastblog1.blogspot.com/2019/11/best-free-photo-...

bmer 7y ago

I am surprised there is no mention of hdf5 (via h5py). It's what I used to deal with handling simulation data that was getting too big for RAM to handle. Use case: CPU is running a simulation and constantly spitting out data, eventually RAM is not enough to hold said data. Solution: every N simulation steps, store data in RAM onto disk, and then continue simulating. N must be chosen judicially so as to balance time cost of writing to disk (don't want to do it too often). I figure this is what is referred to as "chunking" in the article? Why not list some packages that can help one chunk? Overall opinions on this method? Could it be done better?

CreRecombinase 7y ago
This is exactly what HDF5 was built for. Figuring out how often to persist to disk is going to depend on a number of factors. If you want to get fancy you can dedicate a thread to I/O but that gets hairy quickly. You also might want to look into fast compression filters like blosc/lzf as a way of spending down some of your surplus CPU budget.
JBorrow 7y ago
That depends - we use HDF5 to store data from huge simulations (~1TB/snap) which are then obviously too large to analyse on a single machine. The benefit of HDF5 is that it allows for very easy slicing of data. So 'chunking' where I load e.g. 10% of one dataset at once is very simple with HDF5.

miles_matthias 7y ago

Just want to compliment how well written this article is. A lot of technical articles lack the context or basic background (“why”) and this article does a great job.

SlowRobotAhead 7y ago
Why / Intent is the biggest overlooked aspect of computer science / computer engineering imo. I just wish more technical documentation had a human element of “what we intended” to it.

dschuetz 7y ago

Did I miss something? Why would anyone open and load a 100G file all at once on a 16G machine? Why is there such a file in the first place?

jacquesm 7y ago

I'm missing the most obvious one: check to see if you need all that data. Plenty of times you can get 98% of the quality with a small fraction of the available data. Doing a couple of tests to determine what constitutes a representative sample could save you a ton of time and a ton of money.

ImaCake 7y ago
I spent a few weeks on-and-off between more important study, trying to help a friend process their sequencing data in a bespoke way. I kept trying to write an algorithm that would take about 500 hours to run. I first used Pandas (which is kinda slow) and then tried base python dict() and iterables. Eventually I realised that most of the data was actually redundant if I just counted how many instances of each unique row were in my dataset and then just threw away the extras while keeping the counts for later. My new algorithm did what I wanted in 8 seconds flat and was only a tiny bit more effort to integrate with the counts. My lesson learnt was that I just needed to reduce how much data I was working with first, instead of trying to stuff a multi-gb file into memory!
blablablerg 7y ago
This is the number one thing to check first.

nik_ma 7y ago

Nice article

novaRom 7y ago

There is no simple solution because any compression/decompression costs you computations. If data is stored uncompressed, it takes more space but access takes less time than if the data were stored compressed.

ak39 7y ago

When your data doesn't fit in memory: SQLite

lytefm 7y ago
Yeah for me this was also the obvious solution when I had to extract information from ~80 GB of tabular data. It's not the most trendy tool, but it did the job extremely well and with little effort. Just be sure to only create an index after having inserted all the data...
- ak39 7y ago
  Correct. Drop indexes for inserts and recreate after bulk inserts. Also, another hint: process all inserts in the bulk in a single transaction. I was amazed at the speed that SQLite ingests data! Speed demon! (Don’t forget PRAGMA synchronous OFF too)

drej 7y ago

One can efficiently stream data even when there's a need to combine multiple streams. I oftentimes have data sorted on its ID, for instance (usually when it comes from a database), and then can easily join and group by this ID (the same way `uniq` would). All using Python's standard library, here's a quick post I wrote about this. I last used it a week ago and got from 950 MB RAM usage down to about 45 megs. https://kokes.github.io/blog/2018/11/25/merging-streams-python.html https://kokes.github.io/blog/2018/11/25/merging-streams-pyth...

alanbernstein 7y ago

Want to compress and index your data at the same time? Use roaring bitmaps! A bitmap representation of data is surprisingly flexible for computation, and roaring uses some clever tricks to do that with high performance. For additional scalability, try pilosa, a distributed database built on top of roaring (I work for the company that maintains pilosa). https://roaringbitmap.org/ https://roaringbitmap.org/ https://www.pilosa.com/ https://www.pilosa.com/

alexcnwy 7y ago

There's a lot of room between a laptop with 16GB of RAM and a "Big Data cluster" - in my experience the easiest solution is to spin up a VM in GCP and crank the RAM way up. It blew my mind when I realized I could add / remove RAM by turning off the instance, dragging a slider, then turning it back on. I also find h5py really useful for creating massive numpy arrays on disk that are too large to fit in memory. I used it to precompute CNN features for a video classification model (much faster than computing on each gradient descent pass) and it makes it easy to read/write parts of a numpy array when the entire numpy array is too big to fit in memory.

stilley2 7y ago
Besides compression, is there an advantage to using h5py over numpy's memmap?

rmuchev 7y ago

If your data needs sorting and does not fit in memory: https://github.com/rmuchev/ExternalSort https://github.com/rmuchev/ExternalSort

snvzz 7y ago

Odd not to see any reference to mmap, which is part of the python library.

RocketSyntax 7y ago

step 1. use a generator instead of a loop https://realpython.com/introduction-to-python-generators/ https://realpython.com/introduction-to-python-generators/

drderidder 7y ago

Somebody needs to tell this guy about a thing called a "database".