Article View: net.arch
Article #2971Re: One really good use for BIG core memory (address sort)
From: John R. Levine
Date: Fri, 03 Oct 1986 23:06
Date: Fri, 03 Oct 1986 23:06
17 lines
1640 bytes
1640 bytes
In article <403@vaxb.calgary.UUCP> radford@calgary.UUCP (Radford Neal) writes:
>
>Bucket sort is not O(n) in time, nor O(k), but O(nlogn). This is
>because the time required to decode the addresses for your huge
>memories is logarithmic in the size of the memory.
Not really true -- memory addresses are not decoded by a tree but more
typically by broadcasting the address and having all of the memory units
look for their own addresses in parallel. More realistically, by the time
you take into account caches, pipelined buses, interleaved memory and all
the other speed up tricks commonly done in hardware, the address decode time
is the least of your problems.
--
John R. Levine, Javelin Software Corp., Cambridge MA +1 617 494 1400
{ ihnp4 | decvax | cbosgd | harvard | yale }!ima!johnl, Levine@YALE.EDU
The opinions expressed herein are solely those of a 12-year-old hacker
who has broken into my account and not those of any person or organization.
Technical Details
Message-ID:
<236@ima.UUCP>Path:
arc1-ca.pugleaf.net!utzoo!mnetor!seismo!columbia!rutgers!caip!clyde!ima!johnlReferences:
<600@sdcc12.UUCP> <7960@lanl.ARPA> <5559@decwrl.DEC.COM> <403@vaxb.calgary.UUCP> <15878@ucbvax.BERKELEY.EDU>Show Full Headers
Complete Article Headers
Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP Path: arc1-ca.pugleaf.net!utzoo!mnetor!seismo!columbia!rutgers!caip!clyde!ima!johnl From: johnl@ima.UUCP (John R. Levine) Newsgroups: net.arch Subject: Re: One really good use for BIG core memory (address sort) Message-ID: <236@ima.UUCP> Date: Fri, 3-Oct-86 19:06:23 EDT Article-I.D.: ima.236 Posted: Fri Oct 3 19:06:23 1986 Date-Received: Mon, 6-Oct-86 18:42:17 EDT References: <600@sdcc12.UUCP> <7960@lanl.ARPA> <5559@decwrl.DEC.COM> <403@vaxb.calgary.UUCP> <15878@ucbvax.BERKELEY.EDU> Reply-To: johnl@ima.UUCP (John R. Levine) Organization: Javelin Software Corporation Lines: 17 Summary: it is not O(n log n)