Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.java.programmer > #33033

Re: Things have 'moved on' apparently

Show all headers | View raw

On Sun, 08 Nov 2015 17:05:47 -0500, Arne Vajhøj wrote:

> On 11/8/2015 4:12 PM, Martin Gregorie wrote:
>> In this case the offending functions were the malloc and B-tree modules
>> in the C standard library for DEC's Alpha servers running TrueUNIX.
>>
>> The root problem was that the OS was Mach-based and the implementation
>> seemed to use a single-threaded process to implement each low level
>> clib function: at least, we found this problem in several parts of the
>> OS. Maybe this is the main reason that Mach message-passing
>> micro-kernel architectures have largely disappeared, but I digress...
>>
>> The effect was that, because the btree routine used three chunks of
>> memory for each node (IIRC one for key, one for data, one for the three
>> pointers), so that lookups (which added unknown nodes to the tree)
>> bottle-
>> necked on the malloc() process with three calls per node added. We
>> needed something like 7,000 lookups/sec but couldn't break 800.
>>
>> So I rewrote the btree functions to use only one struct per node, which
>> gave an immediate speedup to better than 1500 lookups/sec.
>>
>> More checks showed that now the sbrk() function that malloc() called
>> each time it needed to extend process heap memory had the same problem.
>> So, I changed my code to use malloc() to grab MB-sized chunks of heap
>> space and and wrote an application level function that allocated btree
>> nodes in my chunk of heap and asked for more when it was needed. This
>> gave me 25,000 looks/sec: job done!
> 
> Isn't that what __mingrow was supposed to do in a more transparent way?
>
'locate' doesn't find __mingrow (or mingrow) in my development 
environment. The pnly references I can find are in relation to a C# 
priority queue: this all happened long before C# existed.

However, I suppose I could have used sbrk() or brk() to collect big 
chunks of heap space instead of malloc(), but the effect would have been 
minimal and in any case use of malloc() is preferred to either brk() or 
sbrk().

Malloc() is pretty transparent and, it turned out that my trick of 
building a list of pointers to large separate blocks of heap space paid 
off later. 

I should add that the Btrees (there was more than one) were used as fast 
lookups to translate large (19 byte) keys into 32 bit soft dbks: both  
ended up as dimensions in a star schema that were updated each time 
another batch of data was loaded into the datawarehouse. Since a key 
values could appear in up to three columns in the fact table, we 
preferred to use the sdbkeys there rather than the actual key values 
because doing this gave us a substantial amount of data compression in 
what was a very large data warehouse for the time. Anyway, when the 
system started up one of its first tasks was to read the dimensions and 
create Btrees from it. After the main Btree exceeded 100M key values, 
people started to complain about the start-up time. This was easy to fix: 
periodically, and as part of shutdown the lookup processes simply wrote 
each of their heap chunks to disk as binary data. Startup became much 
faster, since the processes just read each chunk back into memory as part 
of initialisation. 

It didn't matter where the chunks ended up in process address space since 
all addressing inside a chunk was a simple offset, so no translation was 
needed during the save and restore operations.


-- 
martin@   | Martin Gregorie
gregorie. | Essex, UK
org       |

Back to comp.lang.java.programmer | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

Things have 'moved on' apparently Eternal Hope <laughingspam99@gmail.com> - 2015-11-06 12:32 +0000
  Re: Things have 'moved on' apparently Kevin McMurtrie <mcmurtrie@pixelmemory.us> - 2015-11-06 08:25 -0800
    Re: Things have 'moved on' apparently Eric Douglas <e.d.programmer@gmail.com> - 2015-11-06 12:02 -0800
      Re: Things have 'moved on' apparently Jerry Stuckle <jstucklex@attglobal.net> - 2015-11-06 19:46 -0500
        Re: Things have 'moved on' apparently Martin Gregorie <martin@address-in-sig.invalid> - 2015-11-07 17:21 +0000
          Re: Things have 'moved on' apparently Jerry Stuckle <jstucklex@attglobal.net> - 2015-11-07 12:50 -0500
        Re: Things have 'moved on' apparently Eric Douglas <e.d.programmer@gmail.com> - 2015-11-09 05:37 -0800
          Re: Things have 'moved on' apparently Jerry Stuckle <jstucklex@attglobal.net> - 2015-11-09 09:00 -0500
          Re: Things have 'moved on' apparently Martin Gregorie <martin@address-in-sig.invalid> - 2015-11-09 14:56 +0000
          Re: Things have 'moved on' apparently Martin Gregorie <martin@address-in-sig.invalid> - 2015-11-09 19:25 +0000
      Re: Things have 'moved on' apparently Arne Vajhøj <arne@vajhoej.dk> - 2015-11-07 21:57 -0500
    Re: Things have 'moved on' apparently Arne Vajhøj <arne@vajhoej.dk> - 2015-11-07 22:02 -0500
      Re: Things have 'moved on' apparently leif.roar@dimnakorr.com - 2015-11-08 02:00 -0600
        Re: Things have 'moved on' apparently Arne Vajhøj <arne@vajhoej.dk> - 2015-11-08 08:44 -0500
          Re: Things have 'moved on' apparently leif.roar@dimnakorr.com - 2015-11-08 13:08 -0600
        Re: Things have 'moved on' apparently Robert Klemme <shortcutter@googlemail.com> - 2015-11-08 18:54 +0100
          Re: Things have 'moved on' apparently Martin Gregorie <martin@address-in-sig.invalid> - 2015-11-08 21:12 +0000
            Re: Things have 'moved on' apparently Arne Vajhøj <arne@vajhoej.dk> - 2015-11-08 17:05 -0500
              Re: Things have 'moved on' apparently Martin Gregorie <martin@address-in-sig.invalid> - 2015-11-08 23:24 +0000
                Re: Things have 'moved on' apparently Arne Vajhøj <arne@vajhoej.dk> - 2015-11-08 19:40 -0500
                Re: Things have 'moved on' apparently Jerry Stuckle <jstucklex@attglobal.net> - 2015-11-08 21:32 -0500
                Re: Things have 'moved on' apparently Martin Gregorie <martin@address-in-sig.invalid> - 2015-11-09 15:15 +0000
      Re: Things have 'moved on' apparently Kevin McMurtrie <mcmurtrie@pixelmemory.us> - 2015-11-08 12:10 -0800
        Re: Things have 'moved on' apparently Jerry Stuckle <jstucklex@attglobal.net> - 2015-11-08 16:00 -0500
        Re: Things have 'moved on' apparently Arne Vajhøj <arne@vajhoej.dk> - 2015-11-08 16:51 -0500
  Re: Things have 'moved on' apparently Jan Burse <janburse@fastmail.fm> - 2015-11-08 00:55 +0100
  Re: Things have 'moved on' apparently Arne Vajhøj <arne@vajhoej.dk> - 2015-11-07 21:28 -0500
    Re: Things have 'moved on' apparently Arne Vajhøj <arne@vajhoej.dk> - 2015-11-07 21:36 -0500
  Re: Things have 'moved on' apparently leif.roar@dimnakorr.com - 2015-11-08 02:12 -0600
  Re: Things have 'moved on' apparently askfor <askfor@nowhere.net> - 2015-11-09 18:02 +0100
  Re: Things have 'moved on' apparently Kevin McMurtrie <mcmurtrie@pixelmemory.us> - 2015-11-10 22:32 -0800
    Re: Things have 'moved on' apparently Eternal Hope <laughingspam99@gmail.com> - 2015-11-11 07:52 +0000
      Re: Things have 'moved on' apparently ross.finlayson@gmail.com - 2015-11-19 23:28 -0800

csiph-web