News for hackers. Stuff that matters.

A comment on Finger Trees: A Simple General-Purpose Data Structure (2006). Parent comment

Re:Finger Trees: A Simple General-Purpose Data Structure (2006) by HelloNurse on Tuesday December 27, 2016 @12:47PM (#13264626)
An OS kernel has no business maintaining, and even less business accessing in bulk, large data structures that are performance-critical enough to worry about coherent memory access. It is also an infrastructure-deprived environment in which swapping around pointers to implement a linked list with correct locking is relatively easy to get right but allocating vectors is out of the question.
[ Parent | on HN ]
Re:Finger Trees: A Simple General-Purpose Data Structure (2006) by dom0 on Tuesday December 27, 2016 @01:06PM (#13264753)
> An OS kernel has no business maintaining, and even less business accessing in bulk, large data structures that are performance-critical enough to worry about coherent memory access

File systems are usually part of the kernel.

[ Parent | on HN ]
Re:Finger Trees: A Simple General-Purpose Data Structure (2006) by scott_s on Tuesday December 27, 2016 @02:19PM (#13265406)
File systems tend not to have large data structures. They are relatively modest data structures which manage bulk access to large blocks of data. A subtle distinction, but important in this context.
[ Parent | on HN ]
Re:Finger Trees: A Simple General-Purpose Data Structure (2006) by IgorPartola on Tuesday December 27, 2016 @08:05PM (#13267671)
Really? Even huge volumes with loads of tiny files? Mail and Usenet servers? Build servers? What is your definition of large and modest here?
[ Parent | on HN ]
Re:Finger Trees: A Simple General-Purpose Data Structure (2006) by rosser on Tuesday December 27, 2016 @09:29PM (#13267986)
The data structures under discussion here are those used to track individual files. Yes, there can be squillions of them, but as data structures, they are, in fact, rather modest.
[ Parent | on HN ]