Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!uunet!mcsun!ukc!dcl-cs!aber-cs!athene!pcg From: pcg@cs.aber.ac.uk (Piercarlo Grandi) Newsgroups: comp.lang.misc Subject: Re: C's sins of commission Message-ID: Date: 14 Nov 90 15:16:03 GMT References: <27376@megaron.cs.arizona.edu> <-M.6315@xds13.ferranti.com> Sender: aro@aber-cs.UUCP Organization: Coleg Prifysgol Cymru Lines: 54 Nntp-Posting-Host: odin In-reply-to: peter@ficc.ferranti.com's message of 13 Nov 90 20:58:19 GMT On 13 Nov 90 20:58:19 GMT, peter@ficc.ferranti.com (Peter da Silva) said: peter> Piercarlo Grandi: pcg> Ah no, this cannot pass. Lists and trees are *implementations*, and pcg> when you draw them you draw specific encodings of such pcg> implementations. peter> David Gudeman: gudeman> No, this cannot pass. Lists and trees are mental structures gudeman> that humans use to visualize things. peter> While I'm generally in the bit-bangers camp, I must agree with peter> Piercarlo here. I am a bit banger too, mate... peter> Lists, trees, tries, and so on are methods of implementing these peter> databases in efficient ways. There's nothing fundamental about peter> them. [ ... ] The problem is that there's no language I know of peter> that really lets you get away with writing your program in terms peter> of relations and get within an order of magnitude in speed of a peter> well-written lower level implementation. As to this I have good news! DBMSes and 4GLs are often (anectodal but frequent evidence) impressively *faster* than any ad-hoc program that does the same. NOTE: *the same*, not similar but much much simpler. If you are manipulating large masses of data in complicated ways, which is most people want to do, a well written DBMS is going to be way ahead of any well written lower level solution. Notice that you *can* for a very important problem outrun a well written DBMS with diabolically well written low level code, but this is a rare case. The same applies for example to sort utilities -- normally it takes a lot of effort to beat a well written generic sort utility on any system I know of. The database approach is also being applied to in-memory databases, both relational or OO. They are usually well within an order of magnitude of using explicit ad hoc trees and lists, and may be even faster, if (and again very few are well written) they pay attention to paging issues, which normally even well written tree and list packages ignore. For example: an incore database may use B+ trees, which have an immensely better, if its blocks are suitably aligned and sized, locality profile than most garden variety trees. Again, many programs, either in-memory or on-disk, are sophisticated and large enough to be considered minro DBMSes. Too bad they are not designed as such... -- Piercarlo Grandi | ARPA: pcg%uk.ac.aber.cs@nsfnet-relay.ac.uk Dept of CS, UCW Aberystwyth | UUCP: ...!mcsun!ukc!aber-cs!pcg Penglais, Aberystwyth SY23 3BZ, UK | INET: pcg@cs.aber.ac.uk