home *** CD-ROM | disk | FTP | other *** search
/ Fresh Fonts 1 / freshfonts1.bin / bbs / programs / amiga / makeindex.lha / makeindex-2.12 / src / NOTES < prev    next >
Text File  |  1991-07-26  |  3KB  |  85 lines
  1.          Investigation of Size Reduction in MakeIndex
  2.                 [25-Jul-1991]
  3.  
  4. Joachim Schrod in his work on MakeIndex 3.0 (to be reported at
  5. EuroTeX'91 in Paris, September 1991) found that substantial
  6. storage economizations in MakeIndex are possible by dynamically
  7. allocating some arrays.  Since that version is not yet available, it
  8. seemed worthwhile to try to apply such changes to version 2.10, making
  9. version 2.11.
  10.  
  11. The major memory consumption in MakeIndex is by the arrays af[][] and
  12. sf[][] in
  13.  
  14. #define FIELD_MAX     3
  15. #define STRING_MAX    256
  16.  
  17. typedef struct KFIELD
  18. {
  19.     char    sf[FIELD_MAX][STRING_MAX]; /* sort key */
  20.     char    af[FIELD_MAX][STRING_MAX]; /* actual key */
  21. ...
  22. }       FIELD, *FIELD_PTR;
  23.  
  24. These arrays are referenced in genind.c, scanid.c, and sortid.c.  They
  25. are defined in mkind.h, and initialized to empty strings in scanid.c.
  26.  
  27. Each index entry has one such struct KFIELD slot, and with current
  28. dimension limits, sizeof(FIELD) == 1844.  book.idx has 4241 index
  29. entries, so we need 1844*4241 = 7820404 bytes of dynamic storage.
  30. However, book.idx is only 142027 bytes long, and in entry, 16
  31. characters ("\indexentry{}{}") need not be stored; the true storage
  32. requirement is therefore 142027 - 4241*16 = 74171 so 99.05% of the
  33. storage is being wasted,
  34.  
  35. After sorting and removal of duplicate lines, book.idx reduces to
  36. 85935 bytes and 2531 entries, so the actual storage required is
  37. 1844*2531 = 4667164 bytes; the wastage is still high: 98.4%.
  38.  
  39. If we change to
  40.  
  41. typedef struct KFIELD
  42. {
  43.     char    *sf[FIELD_MAX]; /* sort key */
  44.     char    *af[FIELD_MAX]; /* actual key */
  45. ...
  46. }       FIELD, *FIELD_PTR;
  47.  
  48. then sizeof(FIELD) = 332, and the required storage is 332*2531 =
  49. 840292 bytes.  This is still too large for an IBM PC.  However, KFIELD
  50. also contains
  51.  
  52.     char    encap[STRING_MAX];         /* encapsulator */
  53.  
  54. and that field is only rarely used, so by dynamically allocating it
  55. when needed, we can reduce the KFIELD node storage by 256 - 4 = 252
  56. bytes, reducing sizeof(FIELD) to 80 bytes.  For book.idx, we then need
  57. 80*2531 = 202480 bytes, and that should be small enough to run on the
  58. PC.
  59.  
  60. encap is used in genind.c, scanid.c, and sortid.c, and defined in
  61. mkind.h.
  62.  
  63. We can handle dynamic allocation of af[] and sf[] three ways: (1)
  64. initialize them both to (char*)NULL, then allocate space as needed,
  65. (2) initialize them both to calloc(1), and (3) initialize them both to
  66. a constant empty string, "".  MakeIndex makes many references to the
  67. first character (*af[i] or af[i][0]), the first scheme would require
  68. many changes to avoid dereferencing NULL pointers.  The second scheme
  69. would not have this problem, but would require a lot of overhead in
  70. malloc'ing 1-character blocks.  The third scheme seems the best
  71. choice, and requires few changes; no free() or realloc() calls are
  72. made by MakeIndex, so we need take no precautions about attempting to
  73. free or reallocate constant string storage.
  74.  
  75. Examination of the code in genind.c, scanid.c, and sortid.c which
  76. references af[] and sf[] shows that changes are needed only in
  77. scanid.c, where we introduce a new function, make_string(), to handle
  78. the dynamic allocation of strings when needed.  Similarly, of the
  79. encap[] uses in genind.c, scanid.c, and sortid.c, only scanid.c needs
  80. changes.  The definition of struct KFIELD in mkind.h must be updated
  81. so that af, sf, and encap become pointers to strings, rather than
  82. arrays of characters.
  83.  
  84.  
  85.