From mboxrd@z Thu Jan 1 00:00:00 1970 From: bakul at bitblocks.com (Bakul Shah) Date: Sun, 12 Jan 2020 17:41:06 -0800 Subject: [COFF] [TUHS] Tech Sq elevator [ really type-checking ] In-Reply-To: Your message of "Sun, 12 Jan 2020 20:23:11 -0500." References: <202001122225.00CMPc9S085970@tahoe.cs.Dartmouth.EDU> <202001122340.00CNeef0604557@darkstar.fourwinds.com> Message-ID: <20200113014113.DB51E156E42E@mail.bitblocks.com> On Sun, 12 Jan 2020 20:23:11 -0500 Dan Cross wrote: > > -TUHS, +COFF, in line with Warren's wishes. > > On Sun, Jan 12, 2020 at 7:36 PM Bakul Shah wrote: > > > There is similar code in FreeBSD kernel. Embedding head and next ptrs > > reduces > > memory allocation and improves cache locality somewhat. Since C doesn't > > have > > generics, they try to gain the same functionality with macros. See > > > > https://github.com/freebsd/freebsd/blob/master/sys/sys/queue.h > > > > Not that this is the same as what Linux does (which I haven't dug into) but > > I suspect they may have had similar motivation. > > > > I was actually going to say, "blame Berkeley." As I understand it, this > code originated in BSD, and the Linux implementation is at least inspired > by the BSD code. There was code for singly and doubly linked lists, queues, > FIFOs, etc. > > I can actually understand the motivation: lists, etc, are all over the > place in a number of kernels. The code to remove an element from a list is > trivial, but also tedious and repetitive: if it can be wrapped up into a > macro, why not do so? It's one less thing to mess up. In late '90s when I first came across code in the FreebSD kernel, as a Scheme-phile I instinctively disliked it. But upon reflection and considering doing it the lisp way -- car,cdr, where car points to a data stucture, I realized this was better, The list way wouldn't have helped and made things worse. Now you may have to either cast the car (whose type would've been void*, which loses type safety) or define data structure specific types and you are back to needing lots of very similar functions. In addition you may now have to lock more data structures to manage these lists. Then consider what happens when an object is on multiple lists. Now you need O(n) operations to remove it from all the lists. And so on. > I agree it's gone off the rails, however. Well, this is "historic unix code" :-)