BTreeSimpleTest.mesa
Copyright Ó 1985, 1986, 1990, 1992, by Xerox Corporation. All rights reserved.
Taft, January 13, 1984 11:15 am
Russ Atkinson (RRA) March 11, 1985 10:04:23 pm PST
Doug Wyatt, December 18, 1986 3:23:30 pm PST
Brian Oki, August 17, 1990 4:23 pm PDT
Willie-s, April 23, 1992 11:34 am PDT
DIRECTORY
Basics,
BasicTime,
BTree,
BTreeSimple,
Commander,
Convert,
IO,
Random,
RealSupport,
Rope,
PFS;
BTreeSimpleTest: CEDAR PROGRAM
IMPORTS BasicTime, BTreeSimple, Commander, Convert, IO, Random, RealSupport, PFS
= {
ROPE: TYPE = Rope.ROPE;
maxEntSize: CARD ¬ 256; -- 1/8 minimum-size page
This entryTable maps a key to a boolean: true if the key exists in the table, false otherwise. The table is as big as the maximum number of key entries allowed. The "count" field keeps track of the number of table entries occupied.
entryTable: REF EntryTable;
EntryTable: TYPE = RECORD [
count: KeyIndex,
exists: PACKED SEQUENCE maxEntries: KeyIndex OF BOOL
];
useFixedSeed: BOOL ¬ TRUE;
markov: Random.RandomStream ¬ NIL;
validateEveryUpdate: BOOL ¬ FALSE;
millisecondsPerPulse: REAL = 1000.0 / RealSupport.IntToReal[BasicTime.MicrosecondsToPulses[1000000]];
OperationArray: TYPE = ARRAY Operation OF CARD ;
Operation: TYPE = {lookup, validate, insert, delete, replace};
UpdateOperation: TYPE = Operation[insert..replace];
KeyIndex: TYPE = CARD;
Error: PUBLIC ERROR [ec: ErrorCode, explanation: ROPE ¬ NIL];
ErrorCode: TYPE = ATOM;
This procedure creates a new, simple, BTree.
Create: PUBLIC PROC [readBacking, writeBacking: IO.STREAM, cacheSize: BTreeSimple.CacheSize ¬ 40, initialize: BOOL ¬ TRUE, pageSize: BTreeSimple.PageSize ¬ 2048, maxEntries: KeyIndex ¬ 10000] RETURNS [tree: BTreeSimple.Tree] = {
IF readBacking = NIL OR writeBacking = NIL THEN ERROR Error[$NoBackingStream, "Backing stream is NIL"];
tree ¬ BTreeSimple.New[];
BTreeSimple.Open[tree: tree, readFile: readBacking, writeFile: writeBacking, pageSize: pageSize, cacheSize: cacheSize, initialize: initialize];
IF initialize THEN {
entryTable ¬ NEW [EntryTable[maxEntries]];
entryTable.count ¬ 0;
Initilize the table entries to false
FOR i: KeyIndex IN [0..entryTable.maxEntries) DO
entryTable.exists[i] ¬ FALSE;
ENDLOOP;
};
RETURN[tree];
};
Insert a key into the BTree.
Insert: PROC [myTree: BTreeSimple.Tree, keyVal: KeyIndex] = {
Create a key from the keyVal argument
key: BTreeSimple.Key = IndexToKey[keyVal];
Choose a size (in bytes) for the value of the Entry.
valueLength: CARD = Random.ChooseInt[markov, 1, maxEntSize];
value: BTreeSimple.Value;
The "value" is merely the original key.
value ¬ NEW[BTreeSimple.ValueObject[valueLength]];
The "value" consists of a sequence of bytes each containing the original key.
FOR i: CARD IN [0..valueLength) DO
value[i] ¬ keyVal;
ENDLOOP;
BTreeSimple.UpdateRecord[tree: myTree, key: key, value: value];
IF ~entryTable.exists[keyVal] THEN {
entryTable.exists[keyVal] ¬ TRUE;
entryTable.count ¬ entryTable.count+1;
};
};
Lookup: PROC [myTree: BTreeSimple.Tree, keyVal: KeyIndex] RETURNS [found: BOOL] = {
key: BTreeSimple.Key = IndexToKey[keyVal];
actualKey: BTreeSimple.InternalKey;
value: BTreeSimple.Value;
[actualKey, value] ¬ BTreeSimple.ReadRecord[tree: myTree, key: key];
IF (found ¬ actualKey#NIL) THEN
FOR i: CARD IN [0..value.length) DO
IF value[i]#keyVal THEN ERROR Error[$wrongContents, "Entry has wrong contents"]; -- entry has wrong contents
ENDLOOP;
RETURN [found];
};
Delete: PROC [myTree: BTreeSimple.Tree, keyVal: KeyIndex] RETURNS [found: BOOL] = {
key: BTreeSimple.Key = IndexToKey[keyVal];
found ¬ BTreeSimple.DeleteKey[tree: myTree, key: key];
IF found THEN {
entryTable.count ¬ entryTable.count-1;
entryTable.exists[keyVal] ¬ FALSE;
};
RETURN [found];
};
IndexToKey: PROC [keyIndex: KeyIndex] RETURNS [key: BTreeSimple.Key] = {
keys from 100000 to 165535, so ASCII collating sequence is same as numeric
RETURN[Convert.RopeFromCard[100000+keyIndex]];
};
keyOfInterest: CARD ¬ LAST[CARD];
RandomOperation: PUBLIC SAFE PROC [myTree: BTreeSimple.Tree] RETURNS [operation: Operation, key: KeyIndex] = TRUSTED {
SELECT Random.ChooseInt[markov, 0, 250+entryTable.count/2] FROM
0 => {
occasionally validate the tree. The frequency of this decreases in proportion to the size of the tree, since each enumeration takes longer as the tree gets larger.
BTreeSimple.Validate[myTree];
operation ¬ validate;
};
ENDCASE => {
otherwise, choose a random key and perform some operation
key ¬ Random.ChooseInt[markov, 0, entryTable.maxEntries-1];
IF key=keyOfInterest THEN ERROR Error[$EncounteredKeyOfInterest, "Interesting key encountered."];
IF entryTable.exists[key] THEN {
key exists. 25% of the time verify that looking it up succeeds, 25% of the time delete it, and 50% of the time replace it with a new entry of a different size.
SELECT Random.ChooseInt[markov, 0, 3] FROM
0 => {
operation ¬ lookup;
IF ~Lookup[myTree, key] THEN ERROR Error[$KeyNotFound, "key doesn't exist"]; -- failed to find existing key
};
1 => {
operation ¬ delete;
IF ~Delete[myTree, key] THEN ERROR Error[$KeyNotFound, "key doesn't exist"]; -- failed to find existing key
};
ENDCASE => {
operation ¬ replace;
Insert[myTree, key];
};
}
ELSE { -- key does not exist. 10% of the time verify that looking it up fails, and 90% of the time insert an entry with this key.
SELECT Random.ChooseInt[markov, 0, 9] FROM
0 => {
operation ¬ lookup;
IF Lookup[myTree, key] THEN ERROR Error[$FoundKey, "found key that shouldn't be there"]; -- found key that it shouldn't have
};
ENDCASE => {
operation ¬ insert;
Insert[myTree, key];
};
};
};
};
EnumerateBackward: PROC [myTree: BTreeSimple.Tree, usePathStk: BOOL ¬ FALSE] = TRUSTED {
EntryProc: UNSAFE PROC [key: BTreeSimple.EntryKey, value: BTreeSimple.EntryValue] = UNCHECKED {
foundKey ¬ BTreeSimple.KeyFromEntry[key];
foundKeyIndex ¬ IF value#NIL THEN value[0] ELSE 0;
};
foundKeyIndex: KeyIndex ¬ entryTable.maxEntries;
foundKey: BTreeSimple.Key ¬ IndexToKey[entryTable.maxEntries];
pathStk: BTreeSimple.PathStk ¬ IF usePathStk THEN BTreeSimple.NewPathStk[] ELSE NIL;
FOR k: KeyIndex DECREASING IN [0..entryTable.maxEntries) DO
IF entryTable.exists[k] THEN {
BTreeSimple.ReadEntry[tree: myTree, key: foundKey, Proc: EntryProc, relation: less, pathStk: pathStk, useExistingPath: usePathStk];
IF foundKey=NIL OR foundKeyIndex#k THEN SIGNAL MissingEntry[k];
};
ENDLOOP;
BTreeSimple.ReadEntry[tree: myTree, key: foundKey, Proc: EntryProc, relation: less, pathStk: pathStk, useExistingPath: usePathStk];
IF foundKey#NIL THEN SIGNAL EnumerateFailedToTerminate;
};
GetEntryCount: PUBLIC SAFE PROC RETURNS [count: CARD] = CHECKED {
RETURN [entryTable.count];
};
GetVMStats: PROC [myTree: BTreeSimple.Tree] RETURNS [refs, reads, writes: CARD, hitPercent: REAL, msPerReadWrite, avgChainLength: REAL] = {
hits, misses, cumChainLength, cumReadWriteTime: CARD;
[hits: hits, misses: misses, reads: reads, writes: writes, cumChainLength: cumChainLength, cumReadWriteTime: cumReadWriteTime] ¬ BTreeSimple.GetStatistics[myTree];
refs ¬ hits+misses;
hitPercent ¬ RealSupport.IntToReal[hits]*100.0 / RealSupport.IntToReal[MAX[refs, 1]];
msPerReadWrite ¬ (RealSupport.IntToReal[cumReadWriteTime] / RealSupport.IntToReal[MAX[reads+writes, 1]]) * millisecondsPerPulse;
avgChainLength ¬ RealSupport.IntToReal[cumChainLength] / RealSupport.IntToReal[MAX[refs, 1]];
};
MissingEntry: SIGNAL [k: KeyIndex] = CODE;
EnumerateFailedToTerminate: SIGNAL = CODE;
FindMissingEntries: PROC [myTree: BTreeSimple.Tree] = {
FOR k: KeyIndex IN [0..entryTable.maxEntries) DO
IF entryTable.exists[k] AND ~Lookup[myTree, k] THEN SIGNAL MissingEntry[k];
ENDLOOP;
};
Taken from InitialCommandsImpl.Time
ElapsedTime: PROC [start, stop: BasicTime.Pulses] RETURNS [ROPE] ~ {
microseconds, seconds: CARD;
digit: CARD;
any: BOOL ¬ FALSE;
text: REF TEXT ¬ NEW[TEXT[8]];
microseconds ¬ BasicTime.PulsesToMicroseconds[stop - start];
seconds ¬ microseconds / 1000000;
microseconds ¬ microseconds MOD 1000000;
THROUGH [0..6) DO
microseconds ¬ microseconds * 10;
digit ¬ microseconds / 1000000;
microseconds ¬ microseconds MOD 1000000;
IF NOT any THEN {
text ¬ Convert.AppendChar[to: text, from: '., quote: FALSE];
any ¬ TRUE;
};
text ¬ Convert.AppendChar[to: text, from: digit + '0, quote: FALSE];
IF microseconds = 0 THEN EXIT;
ENDLOOP;
RETURN [IO.PutFR["%r%g\n", IO.card[seconds], IO.text[text]]];
};
This procedure selects, randomly, some operation to perform on the Btree. It keeps track of two things: the cumulative number of milliseconds required to perform "iteration" operations, and the cumulative number of entries that were changed.
RunTest: PROC [myTree: BTreeSimple.Tree, iterations: CARD] RETURNS [msPerOp: ARRAY Operation OF REAL] = {
index: CARD;
counts: ARRAY Operation OF CARD ¬ ALL [0];
times: ARRAY Operation OF CARD ¬ ALL [0];
IF iterations < 1 THEN ERROR;
FOR index IN [1..iterations] DO
operation: Operation;
k: KeyIndex;
then: BasicTime.Pulses ¬ BasicTime.GetClockPulses[];
[operation: operation, key: k] ¬ RandomOperation[myTree];
times[operation] ¬ times[operation] + (BasicTime.GetClockPulses[] - then);
counts[operation] ¬ counts[operation]+(IF operation=validate THEN BTreeSimple.GetState[myTree].entryCount ELSE 1);
IF validateEveryUpdate AND operation IN UpdateOperation THEN BTreeSimple.Validate[myTree];
ENDLOOP;
This computes the number of milliseconds required for each operation.
FOR operation: Operation IN Operation DO
msPerOp[operation] ¬ (RealSupport.IntToReal[times[operation]]/RealSupport.IntToReal[MAX[counts[operation], 1]]) * millisecondsPerPulse;
ENDLOOP;
};
BTreeSimpleTest: Commander.CommandProc = {
myTree: BTreeSimple.Tree;
writeBacking, readBacking: IO.STREAM;
msPerOp: ARRAY Operation OF REAL;
refs, reads, writes: CARD;
hitPercent, msPerReadWrite, avgChainLength: REAL;
filename: ROPE ¬ NIL;
iterations: CARD ¬ 0;
okay: BOOLEAN ¬ TRUE;
IO.PutRope[cmd.out, "Name of file to hold BTree: "];
filename ¬ IO.GetLineRope[cmd.in];
IF filename = NIL THEN {
filename ¬ "BTreeTest.tree"; -- default filename
};
IO.PutRope[cmd.out, "Number of iterations to perform: "];
iterations ¬ Convert.CardFromRope[IO.GetLineRope[cmd.in] !
Convert.Error => {IO.PutRope[cmd.out, "Error from BTreeSimpleTest: not a number\n"]; RETRY}
];
writeBacking ¬ PFS.StreamOpen[PFS.PathFromRope[filename], $write];
readBacking ¬ PFS.StreamOpen[PFS.PathFromRope[filename], $read];
myTree ¬ Create[readBacking, writeBacking, 500];
[msPerOp] ¬RunTest[myTree, iterations ! Error =>
{IO.PutF[cmd.out, "Error from BTreeSimpleTest: %g - %g\n", IO.atom[ec], IO.rope[explanation]];
CONTINUE};
];
FOR operation: Operation IN Operation DO {
opname: ROPE ¬ NIL;
SELECT operation FROM
lookup => opname ¬ "lookup";
validate => opname ¬ "validate";
insert => opname ¬ "insert";
delete => opname ¬ "delete";
replace => opname ¬ "replace";
ENDCASE;
IO.PutF[cmd.out, " %g = %g msec\n", IO.rope[opname], IO.real[msPerOp[operation]]];
};
ENDLOOP;
IO.PutRope[cmd.out, "\n Virtual memory statistics.\n\n"];
[refs, reads, writes, hitPercent, msPerReadWrite, avgChainLength] ¬ GetVMStats[myTree];
IO.PutF[cmd.out, " %g = %g \n", IO.rope["Hits and misses"], IO.card[refs]];
IO.PutF[cmd.out, " %g = %g \n", IO.rope["Reads"], IO.card[reads]];
IO.PutF[cmd.out, " %g = %g \n", IO.rope["Writes"], IO.card[writes]];
IO.PutF[cmd.out, " %g = %g \n", IO.rope["Percentage hit"], IO.real[hitPercent]];
IO.PutF[cmd.out, " %g = %g \n", IO.rope["Milliseconds per read/write"], IO.real[msPerReadWrite]];
IO.PutF[cmd.out, " %g = %g \n", IO.rope["Average chain length"], IO.real[avgChainLength]];
Flush anything remaining on 'backing' stream, and close it
IO.Flush[writeBacking];
IO.Close[writeBacking];
IO.Close[readBacking];
};
Commander.Register[key: "BTreeSimpleTest", proc: BTreeSimpleTest,
doc: "Test the BTreeSimple package." ];
}.