This might be slightly off-topic, but I'm curious:
> The core of this program is a loop which calculates the number of blocks required to hold the data of file we’re reading by first finding its size. Memory for all the required iovec structures is allocated. We iterate for a count equal to the number of blocks the file size is, allocate block-sized memory to hold the actual data and finally call readv() to read in the data.
My reading of this is that the first readv(2) implementation of cat uses space in O(n) where n is file size. With a very small constant, yes, but still linear in the number of blocks.
Before reading this article, I would have assumed one wanted to write cat to be constant space, and stream one block at a time through user space – i.e. in O(n) number of system calls instead.
When I'm reading this implementation, I'm starting to realise this is the good old space-time tradeoff, where one can either use O(n) space or O(n) system calls. For very small files, the preallocated references are probably preferable, and for bigger files, the streaming approach is better.
Does anyone know of any rules of thumb or approaches to estimate where the cutoff is? Or is it just a matter of benchmarking on various platforms?
> The core of this program is a loop which calculates the number of blocks required to hold the data of file we’re reading by first finding its size. Memory for all the required iovec structures is allocated. We iterate for a count equal to the number of blocks the file size is, allocate block-sized memory to hold the actual data and finally call readv() to read in the data.
My reading of this is that the first readv(2) implementation of cat uses space in O(n) where n is file size. With a very small constant, yes, but still linear in the number of blocks.
Before reading this article, I would have assumed one wanted to write cat to be constant space, and stream one block at a time through user space – i.e. in O(n) number of system calls instead.
When I'm reading this implementation, I'm starting to realise this is the good old space-time tradeoff, where one can either use O(n) space or O(n) system calls. For very small files, the preallocated references are probably preferable, and for bigger files, the streaming approach is better.
Does anyone know of any rules of thumb or approaches to estimate where the cutoff is? Or is it just a matter of benchmarking on various platforms?