Why C for operating systems
in [General Programming]
|
From: Chris M. Thomasson on 7 Dec 2009 09:06 "bartc" <bartc(a)freeuk.com> wrote in message news:8Y6Tm.12846$Ym4.4120(a)text.news.virginmedia.com... > > "Chris M. Thomasson" <no(a)spam.invalid> wrote in message > news:wm5Tm.41628$cd7.2227(a)newsfe04.iad... >> "Pascal J. Bourguignon" <pjb(a)informatimago.com> wrote in message >> news:87ocmbf837.fsf(a)galatea.local... >>> "Chris M. Thomasson" <no(a)spam.invalid> writes: >>> >>>> Why do I like C: >>>> >>>> http://groups.google.com/group/comp.lang.c/browse_frm/thread/b11dafcbe1079934 >>> >>> In Common Lisp, you just use (declare (dynamic-extend <variable>)), >>> and the compiler implements this "region" allocation (or any other >>> similar scheme) automatically. >> >> That's great! However, I don't use Lisp. > > You should; Lisp is magical. No matter how obscure the requirement, there > always seems to exist some one-liner like this to solve the problem. Lisp looks like a fine language indeed. >> how to do that in a HLL. I am also not sure how to efficiently implement >> a Judy Array in a HLL: > > In Lisp, almost certainly there will be something like (declare judy-array > m n). At least, that's the impression I get. I don't quite understand what you mean. I was writing about actually implementing the Judy Array from scratch. Can that be done in Lisp?
From: Chris M. Thomasson on 7 Dec 2009 09:29 "Pascal J. Bourguignon" <pjb(a)informatimago.com> wrote in message news:87k4wzf72o.fsf(a)galatea.local... > "James" <no(a)spam.invalid> writes: > >> "Pascal J. Bourguignon" <pjb(a)informatimago.com> wrote in message >> news:87ws0zfxgf.fsf(a)galatea.local... >>> "BGB / cr88192" <cr88192(a)hotmail.com> writes: >>> >>> [... basically that GC and big runtimes is a drag to system >>> programming ...] >>> >>> Have a look at Modula-3. This is a language specifically designed for >>> system programming and specifically including a garbage collector. >> >> Garbage collected bootloader and Kernel? > > Well, if you really need to manage so much memory to write a bootloader, > why not. > > And for a kernel, you definitely need to manage memory, so a garbage > collector may indeed be quite useful. Try to convince Linus Torvalds that a full-blown GC in the Kernel would be better and more efficient than using the RCU algorithm. >> Can I really use Haskell or Modula-3 to create that? What about a >> garbage collected Kernel with exceptions that beats the heck out of >> a Kernel written in CO and assembly language? Is that possible? > > Of course. In general, the quality of the kernels and systems written > in other languages than C is higher. > > (Perhaps an interlude with "The Unix Haters Handbook" > http://simson.net/ref/ugh.pdf would be in order here ;-)) :^) <OT rant> The part where the author basically describes garbage collection as being a silver bullet of sorts is very amusing to me. Especially the part where he says one of the advantages of porting an algorithm to a GC environment is that a plurality of the bugs will be fixed! WOW! I have had mixed experiences with GC. Here is something that pisses me off about Java: http://groups.google.com/group/comp.lang.c++/msg/4c68f9617fc301e7 What a damn joke! IMO, you can't really beat the efficiency of clever manual memory management. Heck, manual memory management can even be highly beneficial in a 100% full GC environment. Take a scenario in which a thread wanted to push some data onto a queue, and this required an internal node to be created so the data could be linked into the data-structure and consumed by another thread. If this action occurs frequently, then a shi% load of internal nodes will be created and tremendous pressure will be put on the poor GC. However, if we used a cache of nodes and manually popped/pushed nodes to/from the cache, well, that would take a lot of the burden off the GC. However, the act of using the cache IS manual memory management in and of itself. </OT rant>
From: Pascal J. Bourguignon on 7 Dec 2009 09:39 "Chris M. Thomasson" <no(a)spam.invalid> writes: > I don't quite understand what you mean. I was writing about actually > implementing the Judy Array from scratch. Can that be done in Lisp? Of course, you can implement any algorithm in Lisp. What would make you think that it cannot be done in Lisp? By the way, in Common Lisp, there is not one but THREE ways to compute with bits: either as integers, like in C, as vectors or multidimentional arrays of bits, or as boolean. As integers: (setf *read-base* 2. *print-base* 2.) --> 10 (logand 1100 1010) --> 1000 (Well, more fun than in C, since you can set the default base to 2, (any base from two to thirty-six), so that you don't have to convert numbers to octal, hexadecimal or decimal yourself...) As bit vectors: (bit-and #*1100 #*1010) --> #*1000 As bit arrays (more than two dimensions are possible too): (bit-and #2A(#*1111 #*1001 #*1001 #*1001) #2A(#*1111 #*1110 #*1100 #*1000)) --> #2A(#*1111 #*1000 #*1000 #*1000) As booleans: (mapcar (lambda (a b) (and a b)) '(t t nil nil) '(t nil t nil)) --> (T NIL NIL NIL) -- __Pascal Bourguignon__
From: Pascal J. Bourguignon on 7 Dec 2009 09:48 "Chris M. Thomasson" <no(a)spam.invalid> writes: > "Pascal J. Bourguignon" <pjb(a)informatimago.com> wrote in message > news:87k4wzf72o.fsf(a)galatea.local... >> "James" <no(a)spam.invalid> writes: >> >>> "Pascal J. Bourguignon" <pjb(a)informatimago.com> wrote in message >>> news:87ws0zfxgf.fsf(a)galatea.local... >>>> "BGB / cr88192" <cr88192(a)hotmail.com> writes: >>>> >>>> [... basically that GC and big runtimes is a drag to system >>>> programming ...] >>>> >>>> Have a look at Modula-3. This is a language specifically designed for >>>> system programming and specifically including a garbage collector. >>> >>> Garbage collected bootloader and Kernel? >> >> Well, if you really need to manage so much memory to write a >> bootloader, why not. >> >> And for a kernel, you definitely need to manage memory, so a garbage >> collector may indeed be quite useful. > > Try to convince Linus Torvalds that a full-blown GC in the Kernel > would be better and more efficient than using the RCU algorithm. > > > > >>> Can I really use Haskell or Modula-3 to create that? What about a >>> garbage collected Kernel with exceptions that beats the heck out of >>> a Kernel written in CO and assembly language? Is that possible? >> >> Of course. In general, the quality of the kernels and systems written >> in other languages than C is higher. >> >> (Perhaps an interlude with "The Unix Haters Handbook" >> http://simson.net/ref/ugh.pdf would be in order here ;-)) > > :^) > > > > > <OT rant> > The part where the author basically describes garbage collection as > being a silver bullet of sorts is very amusing to me. Especially the > part where he says one of the advantages of porting an algorithm to a > GC environment is that a plurality of the bugs will be fixed! WOW! > > > I have had mixed experiences with GC. Here is something that pisses me > off about Java: > > > http://groups.google.com/group/comp.lang.c++/msg/4c68f9617fc301e7 > > > What a damn joke! IMO, you can't really beat the efficiency of clever > manual memory management. Heck, manual memory management can even be > highly beneficial in a 100% full GC environment. Take a scenario in > which a thread wanted to push some data onto a queue, and this > required an internal node to be created so the data could be linked > into the data-structure and consumed by another thread. If this action > occurs frequently, then a shi% load of internal nodes will be created > and tremendous pressure will be put on the poor GC. However, if we > used a cache of nodes and manually popped/pushed nodes to/from the > cache, well, that would take a lot of the burden off the GC. However, > the act of using the cache IS manual memory management in and of > itself. > </OT rant> > You're perfectly right. But not for a general programming environment. Manual memory management is of course useful in some very specific cases. It should not be the default mode of operations. For 99% of the programmers, it should not be their concern, no more than device drivers are their concern. By the same token, when we consider operating systems, and again, given the performance of today computers, it should not be a concern for 99% of the operating system developers. Sure, you have unix and linux where you may have good reasons to implement kernel memory management manually. But for a lot of other kinds of operating systems (most being yet to be invented), you don't care about manual kernel memory management, and a garbage collector in the kernel could be a perfectly good solution. Instead of writing yet another unix implementation (Linus wasn't the first to make such a clone, let's pray he'll be amongst the lasts), people interested in operating system writing today should try to invent something else, and concentrate on other features than lowly manual memory management. (And yes, in some lisp programs, buffers are preallocated, and reused like you describe it, but often a generational garbage collector can be as efficient as this manual memory management). -- __Pascal Bourguignon__
From: Chris M. Thomasson on 7 Dec 2009 10:08
"Pascal J. Bourguignon" <pjb(a)informatimago.com> wrote in message news:87r5r6etl5.fsf(a)galatea.local... > "Chris M. Thomasson" <no(a)spam.invalid> writes: >> I don't quite understand what you mean. I was writing about actually >> implementing the Judy Array from scratch. Can that be done in Lisp? > > Of course, you can implement any algorithm in Lisp. Can I dynamically allocate an object in Lisp on a specific alignment boundary, and get a pointer to it that I can pack with a reference count and use single-word atomic operations to mutate it? Say I want object on 4096 byte boundary, and I want to steal bits in pointer to pack in meta-data. For instance, how would I implement the following proxy garbage collection algorithm in Lisp: http://webpages.charter.net/appcore/misc/pc_sample_c.html http://webpages.charter.net/appcore/misc/pc_sample_h.html Please excuse the crude code, it was just a quick proof-of-concept, I did not even bother to check if `malloc()' failed. Anyway, the key aspect of the algorithm is that it does not use double-width compare-and-swap (DWCAS). This is a major plus because the instruction is NOT portable to 64-bit architectures. I get around using DWCAS by packing a reference count into pointers to `pc_deferred_t' data-structures. The memory which makes up `pc_deferred_t' data-structures is aligned to a sufficient enough boundary such that I can pack a reference count [0...127] in there. Therefore, I can use normal single-word CAS on the anchor. BTW, the proxy garbage collection is a solution to memory management in the reader/writer problem. You can use this algorithm to allow for a number of reader threads to iterate through shared data-structures (e.g., linked list) while writer threads are concurrently adding/removing/deallocating items. We can move the discussion over to `comp.programming.threads' if you are interested in such algorithms... > What would make you think that it cannot be done in Lisp? Probablly because I am not familiar with Lisp! ;^) [...] |