Eric Pruitt <eric.pruitt_AT_gmail.com> wrote:
> I think there should be separate implementations for seekable vs
> non-seekable files to avoid buffering the entire contents of
> the file in memory unnecessarily.
In fact, performance could be also improved for non-seekable files
by forcing a seekable context, ie. use a temporary file (that is
seekable), and then perform the function for seekable files on it.
coreutils' tac does this.
But I'm not sure the performance gain is worth the complexity.
On my computer, for a 115M file generated as follows
yes Hello World | head -n10000000
here is the time for this tac implementation, obtained by
`tac <file`.
real 0m 2.08s
user 0m 1.50s
sys 0m 0.54s
and here is for coreutils' implementation:
real 0m 0.35s
user 0m 0.29s
sys 0m 0.05s
Fom this highly scientific test, we can conclude that coreutils'
tac, by using more complex code, achives the same result roughly 6
times faster than this tac implementation.
To take advantage of lseek to achieve better performance, we actually
need to manually buffer the input, and print in reverse each line stored
in the buffer — except if the line is incomplete in which case we have
to keep that part of the buffer, possibly realloc, and read more in reverse.
This brings not-so-useful complexity. The performance gain is not dramatic,
and tac is usually a filter which takes as input relatively little data
(generally less than 115M anyway). So I do not think it is worth the complexity,
or worth the effort, to write such a complex algorithm if the benefit is so
little.
The memory usage of this tac is huge, though. Larger than what a lseek-based
approach could bring.
All in all, I believe this could be worth investigating. I do not know how
to write a _simple_ algorithm that achieves the lseek-based approach (a
complex one is easy to do, but complex algorithms are more error-prone
if incorrectly written, and generally stay as ugly, suky, legacy code),
but if you do, I'd be pleased to implement it.
As a sidenote, sbase's sort(1) also buffers up the whole file before
sorting it. If there is an efficient (ie. lseek-based) way to perform
the function of sort(1) (or tac(1)) without adding sucky complexity to
this suckless project, then it should be implemented. I'm not sure that
such a way exists, sadly.
--
Kind regards,
Elie Le Vaillant
Received on Tue Mar 05 2024 - 00:13:13 CET