diff options
author | Karl Berry <karl@freefriends.org> | 2006-01-17 21:41:51 +0000 |
---|---|---|
committer | Karl Berry <karl@freefriends.org> | 2006-01-17 21:41:51 +0000 |
commit | 487ca4806cc046076293cf6cc5fbba0db282bac7 (patch) | |
tree | 847b412ab5158dd7bdd7ed7e5a4cc3fbca94be32 /Build/source/texk/makeindexk/NOTES | |
parent | a3d3111bfe26b8e5f5bc6049dfb2a4ca2edc7881 (diff) |
texk 1
git-svn-id: svn://tug.org/texlive/trunk@1485 c570f23f-e606-0410-a88d-b1316a301751
Diffstat (limited to 'Build/source/texk/makeindexk/NOTES')
-rw-r--r-- | Build/source/texk/makeindexk/NOTES | 84 |
1 files changed, 84 insertions, 0 deletions
diff --git a/Build/source/texk/makeindexk/NOTES b/Build/source/texk/makeindexk/NOTES new file mode 100644 index 00000000000..ca81552fe53 --- /dev/null +++ b/Build/source/texk/makeindexk/NOTES @@ -0,0 +1,84 @@ + Investigation of Size Reduction in MakeIndex + [25-Jul-1991] + +Joachim Schrod in his work on MakeIndex 3.0 (to be reported at +EuroTeX'91 in Paris, September 1991) found that substantial +storage economizations in MakeIndex are possible by dynamically +allocating some arrays. Since that version is not yet available, it +seemed worthwhile to try to apply such changes to version 2.10, making +version 2.11. + +The major memory consumption in MakeIndex is by the arrays af[][] and +sf[][] in + +#define FIELD_MAX 3 +#define STRING_MAX 256 + +typedef struct KFIELD +{ + char sf[FIELD_MAX][STRING_MAX]; /* sort key */ + char af[FIELD_MAX][STRING_MAX]; /* actual key */ +... +} FIELD, *FIELD_PTR; + +These arrays are referenced in genind.c, scanid.c, and sortid.c. They +are defined in mkind.h, and initialized to empty strings in scanid.c. + +Each index entry has one such struct KFIELD slot, and with current +dimension limits, sizeof(FIELD) == 1844. book.idx has 4241 index +entries, so we need 1844*4241 = 7820404 bytes of dynamic storage. +However, book.idx is only 142027 bytes long, and in entry, 16 +characters ("\indexentry{}{}") need not be stored; the true storage +requirement is therefore 142027 - 4241*16 = 74171 so 99.05% of the +storage is being wasted, + +After sorting and removal of duplicate lines, book.idx reduces to +85935 bytes and 2531 entries, so the actual storage required is +1844*2531 = 4667164 bytes; the wastage is still high: 98.4%. + +If we change to + +typedef struct KFIELD +{ + char *sf[FIELD_MAX]; /* sort key */ + char *af[FIELD_MAX]; /* actual key */ +... +} FIELD, *FIELD_PTR; + +then sizeof(FIELD) = 332, and the required storage is 332*2531 = +840292 bytes. This is still too large for an IBM PC. However, KFIELD +also contains + + char encap[STRING_MAX]; /* encapsulator */ + +and that field is only rarely used, so by dynamically allocating it +when needed, we can reduce the KFIELD node storage by 256 - 4 = 252 +bytes, reducing sizeof(FIELD) to 80 bytes. For book.idx, we then need +80*2531 = 202480 bytes, and that should be small enough to run on the +PC. + +encap is used in genind.c, scanid.c, and sortid.c, and defined in +mkind.h. + +We can handle dynamic allocation of af[] and sf[] three ways: (1) +initialize them both to (char*)NULL, then allocate space as needed, +(2) initialize them both to calloc(1), and (3) initialize them both to +a constant empty string, "". MakeIndex makes many references to the +first character (*af[i] or af[i][0]), the first scheme would require +many changes to avoid dereferencing NULL pointers. The second scheme +would not have this problem, but would require a lot of overhead in +malloc'ing 1-character blocks. The third scheme seems the best +choice, and requires few changes; no free() or realloc() calls are +made by MakeIndex, so we need take no precautions about attempting to +free or reallocate constant string storage. + +Examination of the code in genind.c, scanid.c, and sortid.c which +references af[] and sf[] shows that changes are needed only in +scanid.c, where we introduce a new function, make_string(), to handle +the dynamic allocation of strings when needed. Similarly, of the +encap[] uses in genind.c, scanid.c, and sortid.c, only scanid.c needs +changes. The definition of struct KFIELD in mkind.h must be updated +so that af, sf, and encap become pointers to strings, rather than +arrays of characters. + + |