/* File: table_stats.c
** Author(s): Ernie Johnson
** Contact: xsb-contact@cs.sunysb.edu
**
** Copyright (C) The Research Foundation of SUNY, 1986, 1993-1998
**
** XSB is free software; you can redistribute it and/or modify it under the
** terms of the GNU Library General Public License as published by the Free
** Software Foundation; either version 2 of the License, or (at your option)
** any later version.
**
** XSB is distributed in the hope that it will be useful, but WITHOUT ANY
** WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
** FOR A PARTICULAR PURPOSE. See the GNU Library General Public License for
** more details.
**
** You should have received a copy of the GNU Library General Public License
** along with XSB; if not, write to the Free Software Foundation,
** Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
**
** $Id: table_stats.c,v 1.17 2002/05/31 15:09:03 lfcastro Exp $
**
*/
#include "xsb_config.h"
#include "xsb_debug.h"
#include <stdio.h>
#include "auxlry.h"
#include "cell_xsb.h"
#include "psc_xsb.h"
#include "table_stats.h"
#include "trie_internals.h"
#include "macro_xsb.h"
#include "error_xsb.h"
#include "flags_xsb.h"
#include "debug_xsb.h"
/*==========================================================================*/
/*
* T A B L I N G S T A T I S T I C S
* ===================================
*/
/*
* Recording Current Usage
* -----------------------
*/
NodeStats node_statistics(Structure_Manager *sm) {
NodeStats stats;
SM_CurrentCapacity(*sm, NodeStats_NumBlocks(stats),
NodeStats_NumAllocNodes(stats));
SM_CountFreeStructs(*sm, NodeStats_NumFreeNodes(stats));
NodeStats_NodeSize(stats) = SM_StructSize(*sm);
return stats;
}
/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
HashStats hash_statistics(Structure_Manager *sm) {
HashStats ht_stats;
counter num_used_hdrs;
BTHTptr pBTHT;
BTNptr *ppBTN;
ht_stats.hdr = node_statistics(sm);
num_used_hdrs = 0;
HashStats_NumBuckets(ht_stats) = 0;
HashStats_TotalOccupancy(ht_stats) = 0;
HashStats_NonEmptyBuckets(ht_stats) = 0;
HashStats_BucketSize(ht_stats) = sizeof(void *);
pBTHT = (BTHTptr)SM_AllocList(*sm);
while ( IsNonNULL(pBTHT) ) {
#ifdef DEBUG_ASSERTIONS
/* Counter for contents of current hash table
------------------------------------------ */
counter num_contents = 0;
#endif
num_used_hdrs++;
HashStats_NumBuckets(ht_stats) += BTHT_NumBuckets(pBTHT);
HashStats_TotalOccupancy(ht_stats) += BTHT_NumContents(pBTHT);
for ( ppBTN = BTHT_BucketArray(pBTHT);
ppBTN < BTHT_BucketArray(pBTHT) + BTHT_NumBuckets(pBTHT);
ppBTN++ )
if ( IsNonNULL(*ppBTN) ) {
#ifdef DEBUG_ASSERTIONS
/* Count the objects in each bucket
-------------------------------- */
BTNptr pBTN = *ppBTN;
do {
num_contents++;
pBTN = BTN_Sibling(pBTN);
} while ( IsNonNULL(pBTN) );
#endif
HashStats_NonEmptyBuckets(ht_stats)++;
}
#ifdef DEBUG_ASSERTIONS
/* Compare counter and header values
--------------------------------- */
if ( num_contents != BTHT_NumContents(pBTHT) )
xsb_warn("Inconsistent %s Usage Calculations:\n"
"\tHash table occupancy mismatch.", SM_StructName(*sm));
#endif
pBTHT = BTHT_NextBTHT(pBTHT);
}
if ( HashStats_NumAllocHeaders(ht_stats) !=
(num_used_hdrs + HashStats_NumFreeHeaders(ht_stats)) )
xsb_warn("Inconsistent %s Usage Calculations:\n"
"\tHeader count mismatch: Alloc: %d Used: %d Free: %d",
SM_StructName(*sm), HashStats_NumAllocHeaders(ht_stats),
num_used_hdrs, HashStats_NumFreeHeaders(ht_stats));
return ht_stats;
}
/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
NodeStats subgoal_statistics(Structure_Manager *sm) {
NodeStats sg_stats;
TIFptr tif;
VariantSF pProdSF;
SubConsSF pConsSF;
int nSubgoals;
sg_stats = node_statistics(sm);
nSubgoals = 0;
if ( sm == &smVarSF ) {
for ( tif = tif_list.first; IsNonNULL(tif); tif = TIF_NextTIF(tif) )
if ( IsVariantPredicate(tif) )
for ( pProdSF = TIF_Subgoals(tif); IsNonNULL(pProdSF);
pProdSF = (VariantSF)subg_next_subgoal(pProdSF) )
nSubgoals++;
}
else if ( sm == &smProdSF ) {
for ( tif = tif_list.first; IsNonNULL(tif); tif = TIF_NextTIF(tif) )
if ( IsSubsumptivePredicate(tif) )
for ( pProdSF = TIF_Subgoals(tif); IsNonNULL(pProdSF);
pProdSF = (VariantSF)subg_next_subgoal(pProdSF) )
nSubgoals++;
}
else if ( sm == &smConsSF ) {
for ( tif = tif_list.first; IsNonNULL(tif); tif = TIF_NextTIF(tif) )
if ( IsSubsumptivePredicate(tif) )
for ( pProdSF = TIF_Subgoals(tif); IsNonNULL(pProdSF);
pProdSF = (VariantSF)subg_next_subgoal(pProdSF) )
for ( pConsSF = subg_consumers(pProdSF); IsNonNULL(pConsSF);
pConsSF = conssf_consumers(pConsSF) )
nSubgoals++;
}
else {
xsb_dbgmsg((LOG_DEBUG, "Incorrect use of subgoal_statistics()\n"
"SM does not contain subgoal frames"));
return sg_stats;
}
if ( NodeStats_NumUsedNodes(sg_stats) != nSubgoals )
xsb_warn("Inconsistent Subgoal Frame Usage Calculations:\n"
"\tSubgoal Frame count mismatch");
return sg_stats;
}
/*-------------------------------------------------------------------------*/
/*
* Displaying Current Usage
* ------------------------
*/
void print_detailed_tablespace_stats() {
NodeStats
btn, /* Basic Trie Nodes */
tstn, /* Time Stamp Trie Nodes */
aln, /* Answer List Nodes */
tsi, /* Time Stamp Indices (Index Entries/Nodes) */
varsf, /* Variant Subgoal Frames */
prodsf, /* Subsumptive Producer Subgoal Frames */
conssf; /* Subsumptive Consumer Subgoal Frames */
HashStats
btht, /* Basic Trie Hash Tables */
tstht; /* Time Stamp Trie Hash Tables */
btn = node_statistics(&smTableBTN);
btht = hash_statistics(&smTableBTHT);
varsf = subgoal_statistics(&smVarSF);
prodsf = subgoal_statistics(&smProdSF);
conssf = subgoal_statistics(&smConsSF);
aln = node_statistics(&smALN);
tstn = node_statistics(&smTSTN);
tstht = hash_statistics(&smTSTHT);
tsi = node_statistics(&smTSIN);
printf("\n"
"Table Space Usage\n");
printf(" Current Total Allocation: %12u bytes\n"
" Current Total Usage: %12u bytes\n",
CurrentTotalTableSpaceAlloc(btn,btht,varsf,prodsf,conssf,aln,
tstn,tstht,tsi),
CurrentTotalTableSpaceUsed(btn,btht,varsf,prodsf,conssf,aln,
tstn,tstht,tsi));
printf("\n"
" Basic Tries\n");
printf(" Basic Trie Nodes (%u blocks)\n"
" Allocated: %10u (%8u bytes)\n"
" Used: %10u (%8u bytes)\n"
" Free: %10u (%8u bytes)\n",
NodeStats_NumBlocks(btn),
NodeStats_NumAllocNodes(btn), NodeStats_SizeAllocNodes(btn),
NodeStats_NumUsedNodes(btn), NodeStats_SizeUsedNodes(btn),
NodeStats_NumFreeNodes(btn), NodeStats_SizeFreeNodes(btn));
printf(" Basic Trie Hash Tables (%u blocks)\n"
" Headers: %10u (%8u bytes)\n"
" Used: %10u (%8u bytes)\n"
" Free: %10u (%8u bytes)\n"
" Buckets: %10u (%8u bytes)\n"
" Used: %10u\n"
" Empty: %10u\n"
" Occupancy: %10u BTNs\n",
HashStats_NumBlocks(btht),
HashStats_NumAllocHeaders(btht), HashStats_SizeAllocHeaders(btht),
HashStats_NumUsedHeaders(btht), HashStats_SizeUsedHeaders(btht),
HashStats_NumFreeHeaders(btht), HashStats_SizeFreeHeaders(btht),
HashStats_NumBuckets(btht), HashStats_SizeAllocBuckets(btht),
HashStats_NonEmptyBuckets(btht), HashStats_EmptyBuckets(btht),
HashStats_TotalOccupancy(btht));
printf("\n"
" Subgoal Frames\n"
" Variant Subgoal Frames (%u blocks)\n"
" Allocated: %10u (%8u bytes)\n"
" Used: %10u (%8u bytes)\n"
" Free: %10u (%8u bytes)\n"
" Subsumptive Producer Subgoal Frames (%u blocks)\n"
" Allocated: %10u (%8u bytes)\n"
" Used: %10u (%8u bytes)\n"
" Free: %10u (%8u bytes)\n"
" Subsumptive Consumer Subgoal Frames (%u blocks)\n"
" Allocated: %10u (%8u bytes)\n"
" Used: %10u (%8u bytes)\n"
" Free: %10u (%8u bytes)\n",
NodeStats_NumBlocks(varsf),
NodeStats_NumAllocNodes(varsf), NodeStats_SizeAllocNodes(varsf),
NodeStats_NumUsedNodes(varsf), NodeStats_SizeUsedNodes(varsf),
NodeStats_NumFreeNodes(varsf), NodeStats_SizeFreeNodes(varsf),
NodeStats_NumBlocks(prodsf),
NodeStats_NumAllocNodes(prodsf), NodeStats_SizeAllocNodes(prodsf),
NodeStats_NumUsedNodes(prodsf), NodeStats_SizeUsedNodes(prodsf),
NodeStats_NumFreeNodes(prodsf), NodeStats_SizeFreeNodes(prodsf),
NodeStats_NumBlocks(conssf),
NodeStats_NumAllocNodes(conssf), NodeStats_SizeAllocNodes(conssf),
NodeStats_NumUsedNodes(conssf), NodeStats_SizeUsedNodes(conssf),
NodeStats_NumFreeNodes(conssf), NodeStats_SizeFreeNodes(conssf));
printf("\n"
" Answer List Nodes (%u blocks)\n"
" Allocated: %10u (%8u bytes)\n"
" Used: %10u (%8u bytes)\n"
" Free: %10u (%8u bytes)\n",
NodeStats_NumBlocks(aln),
NodeStats_NumAllocNodes(aln), NodeStats_SizeAllocNodes(aln),
NodeStats_NumUsedNodes(aln), NodeStats_SizeUsedNodes(aln),
NodeStats_NumFreeNodes(aln), NodeStats_SizeFreeNodes(aln));
printf("\n"
" Time Stamp Tries\n"
" Time Stamp Trie Nodes (%u blocks)\n"
" Allocated: %10u (%8u bytes)\n"
" Used: %10u (%8u bytes)\n"
" Free: %10u (%8u bytes)\n",
NodeStats_NumBlocks(tstn),
NodeStats_NumAllocNodes(tstn), NodeStats_SizeAllocNodes(tstn),
NodeStats_NumUsedNodes(tstn), NodeStats_SizeUsedNodes(tstn),
NodeStats_NumFreeNodes(tstn) , NodeStats_SizeFreeNodes(tstn));
printf(" Time Stamp Trie Hash Tables (%u blocks)\n"
" Headers: %10u (%8u bytes)\n"
" Used: %10u (%8u bytes)\n"
" Free: %10u (%8u bytes)\n"
" Buckets: %10u (%8u bytes)\n"
" Used: %10u\n"
" Empty: %10u\n"
" Occupancy: %10u TSTNs\n",
HashStats_NumBlocks(tstht),
HashStats_NumAllocHeaders(tstht), HashStats_SizeAllocHeaders(tstht),
HashStats_NumUsedHeaders(tstht), HashStats_SizeUsedHeaders(tstht),
HashStats_NumFreeHeaders(tstht), HashStats_SizeFreeHeaders(tstht),
HashStats_NumBuckets(tstht), HashStats_SizeAllocBuckets(tstht),
HashStats_NonEmptyBuckets(tstht), HashStats_EmptyBuckets(tstht),
HashStats_TotalOccupancy(tstht));
printf(" Time Stamp Trie Index Nodes (%u blocks)\n"
" Allocated: %10u (%8u bytes)\n"
" Used: %10u (%8u bytes)\n"
" Free: %10u (%8u bytes)\n",
NodeStats_NumBlocks(tsi),
NodeStats_NumAllocNodes(tsi), NodeStats_SizeAllocNodes(tsi),
NodeStats_NumUsedNodes(tsi), NodeStats_SizeUsedNodes(tsi),
NodeStats_NumFreeNodes(tsi), NodeStats_SizeFreeNodes(tsi));
if (flags[TRACE_STA]) {
/* Report Maximum Usages
--------------------- */
update_maximum_tablespace_stats(&btn,&btht,&varsf,&prodsf,&conssf,
&aln,&tstn,&tstht,&tsi);
printf("\n"
"Maximum Total Usage: %12ld bytes\n",
maximum_total_tablespace_usage());
printf("Maximum Structure Usage:\n"
" ALNs: %10u (%8u bytes)\n"
" TSINs: %10u (%8u bytes)\n",
maximum_answer_list_nodes(),
maximum_answer_list_nodes() * NodeStats_NodeSize(aln),
maximum_timestamp_index_nodes(),
maximum_timestamp_index_nodes() * NodeStats_NodeSize(tsi));
}
printf("\n");
}
/*-------------------------------------------------------------------------*/
/*
* Recording Maximum Usage
* -----------------------
*/
/*
* Most of the data structures used in tabling are persistent: table
* info frames, subgoal frames, and the trie nodes and hash tables
* (basic and time-stamped). Therefore, the maximum usage of each of
* these structures at any particular time during an evaluation is the
* same as their current usage. However, there are some structures
* whose usage fluctuates during an evaluation. In particular,
* TimeStamp Indices and answer list nodes are reclaimed upon
* completion. Therefore, we explicitly track their maximum usage at
* those times just prior to reclamation. The following data
* structure maintains the maximum usage for each of these structures.
* And as the (ultimate) maximum usage of a particular structure is
* independent of that of other structures, we also explicitly track
* the maximum utilization of table space.
*/
struct {
counter tsi; /* TS Index Nodes */
counter alns; /* Answer List Nodes */
unsigned long total_bytes; /* total tablespace in bytes */
} maxTableSpaceUsage = {0,0,0};
/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
void reset_maximum_tablespace_stats() {
maxTableSpaceUsage.tsi = maxTableSpaceUsage.alns = 0;
maxTableSpaceUsage.total_bytes = 0;
}
/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
/*
* To be used to facilitate statistical recordings, but in situations
* where one is not currently inspecting results, e.g., when reclaiming
* table space at completion. This procedure queries the current state
* of usage of all table components, and tests whether this is a new
* maximum.
*/
void compute_maximum_tablespace_stats() {
NodeStats tstn, btn, aln, tsi;
NodeStats varsf, prodsf, conssf;
HashStats tstht, btht;
btn = node_statistics(&smTableBTN);
btht = hash_statistics(&smTableBTHT);
varsf = subgoal_statistics(&smVarSF);
prodsf = subgoal_statistics(&smProdSF);
conssf = subgoal_statistics(&smConsSF);
tstn = node_statistics(&smTSTN);
tstht = hash_statistics(&smTSTHT);
tsi = node_statistics(&smTSIN);
aln = node_statistics(&smALN);
update_maximum_tablespace_stats(&btn,&btht,&varsf,&prodsf,&conssf,
&aln,&tstn,&tstht,&tsi);
}
/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
/*
* To be used to facilitate statistical reporting at the moment -- when
* one is currently inspecting results. Presumably one would want to
* independently query the current state of usage of all table
* components for such reporting, so we use these results rather than
* recompute them.
*/
void update_maximum_tablespace_stats(NodeStats *btn, HashStats *btht,
NodeStats *varsf, NodeStats *prodsf,
NodeStats *conssf, NodeStats *aln,
NodeStats *tstn, HashStats *tstht,
NodeStats *tsi) {
unsigned long byte_size;
byte_size = CurrentTotalTableSpaceUsed(*btn,*btht,*varsf,*prodsf,*conssf,
*aln,*tstn,*tstht,*tsi);
if ( byte_size > maxTableSpaceUsage.total_bytes )
maxTableSpaceUsage.total_bytes = byte_size;
if ( NodeStats_NumUsedNodes(*aln) > maxTableSpaceUsage.alns )
maxTableSpaceUsage.alns = NodeStats_NumUsedNodes(*aln);
if ( NodeStats_NumUsedNodes(*tsi) > maxTableSpaceUsage.tsi )
maxTableSpaceUsage.tsi = NodeStats_NumUsedNodes(*tsi);
}
/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
counter maximum_timestamp_index_nodes() {
return (maxTableSpaceUsage.tsi);
}
/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
counter maximum_answer_list_nodes() {
return (maxTableSpaceUsage.alns);
}
/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
unsigned long maximum_total_tablespace_usage() {
return (maxTableSpaceUsage.total_bytes);
}
/*-------------------------------------------------------------------------*/
/*
* Recording and Displaying Operational Counts
* -------------------------------------------
*/
NumSubOps numSubOps = INIT_NUMSUBOPS;
void reset_subsumption_stats() {
NumSubOps initRecord = INIT_NUMSUBOPS;
numSubOps = initRecord;
}
void print_detailed_subsumption_stats() {
printf("Subsumptive Operations\n"
" Subsumptive call check/insert ops: %8u\n"
" * Calls to nonexistent or incomplete tables\n"
" - Producers: %6u\n"
" - Variants of producers: %6u\n"
" - Properly subsumed: %6u\n"
" Resulted in call table entry: %u\n"
" * Calls to completed tables: %6u\n",
NumSubOps_CallCheckInsert, NumSubOps_ProducerCall,
NumSubOps_VariantCall, NumSubOps_SubsumedCall,
NumSubOps_SubsumedCallEntry, NumSubOps_CallToCompletedTable);
printf(" Answer check/insert operations: %8u\n"
" * Actual answer inserts: %6u\n"
" * Derivation ratio (New/Total): %4.2f\n",
NumSubOps_AnswerCheckInsert, NumSubOps_AnswerInsert,
( (NumSubOps_AnswerCheckInsert != 0)
? (float)NumSubOps_AnswerInsert / (float)NumSubOps_AnswerCheckInsert
: 0 ));
printf(" Relevant-answer identify ops: %8u\n"
" Answer-list consumption ops: %8u\n",
NumSubOps_IdentifyRelevantAnswers, NumSubOps_AnswerConsumption);
}
/*==========================================================================*/
syntax highlighted by Code2HTML, v. 0.9.1