home *** CD-ROM | disk | FTP | other *** search
/ Usenet 1994 October / usenetsourcesnewsgroupsinfomagicoctober1994disk1.iso / altsrc / articles / 11120 < prev    next >
Internet Message Format  |  1994-08-15  |  4KB
  1. Path: wupost!psuvax1!news.pop.psu.edu!news.cac.psu.edu!howland.reston.ans.net!cs.utexas.edu!convex!news.duke.edu!godot.cc.duq.edu!toads.pgh.pa.us!hudson.lm.com!ivory.lm.com!not-for-mail
  2. From: devin@telerama.lm.com (Tod McQuillin)
  3. Newsgroups: alt.sources
  4. Subject: Caching mktime(3)
  5. Date: 15 Aug 1994 02:01:47 -0400
  6. Organization: Telerama Public Access Internet, Pittsburgh, PA USA
  7. Lines: 113
  8. Message-ID: <32n0cb$afh@ivory.lm.com>
  9. NNTP-Posting-Host: ivory.lm.com
  10.  
  11. The mktime(3) that comes with BSD net-2 is pretty inefficient; it
  12. seems to do a binary search of the entire time_t space to find the
  13. result.  I discovered this while profiling an invoice generation
  14. program; over half the CPU time was spent in mktime()!
  15.  
  16. Since most of the dates I was converting were within a one month
  17. period, the easiest way to speed it up seemed to be to keep an MRU
  18. cache of the midnights of the dates in question.  The program could
  19. find the time_t of the midnight of the date in the cache and then add
  20. on the hours, minutes and seconds.
  21.  
  22. One bug: the cache will grow needlessly each time you look up the
  23. epoch.  I didn't look up the epoch, so this didn't affect me.
  24.  
  25. This approach worked; the percent time spent in mktime() dropped from
  26. over 60% to barely significant (< 1%).  Here are the results; just
  27. call caching_mktime() instead of mktime():
  28.  
  29. # This is a shell archive.  Save it in a file, remove anything before
  30. # this line, and then unpack it by entering "sh file".  Note, it may
  31. # create directories; files and directories will be owned by you and
  32. # have default permissions.
  33. #
  34. # This archive contains:
  35. #
  36. #    date.h
  37. #    mktime.c
  38. #
  39. echo x - date.h
  40. sed 's/^X//' >date.h << 'END-of-date.h'
  41. Xtime_t caching_mktime(struct tm *tm);
  42. X
  43. X#define MINUTE        60
  44. X#define HOUR        (MINUTE * 60)
  45. X#define DAY        (HOUR * 24)
  46. X
  47. X#define HOURS(time)    ((time) / HOUR)
  48. X#define MINUTES(time)    (((time) - HOURS(time) * HOUR) / MINUTE)
  49. END-of-date.h
  50. echo x - mktime.c
  51. sed 's/^X//' >mktime.c << 'END-of-mktime.c'
  52. X#include <sys/types.h>
  53. X#include <time.h>
  54. X#include <stdlib.h>
  55. X#include <sysexits.h>
  56. X#include <stdio.h>
  57. X#include "date.h"
  58. X
  59. Xtypedef struct cache cache_t;
  60. X
  61. Xstruct cache {
  62. X  struct tm tment;
  63. X  time_t secs;
  64. X  cache_t *next;
  65. X};
  66. X
  67. Xstatic cache_t *mru_cache = NULL;
  68. Xstatic int hits = 0, misses = 0, lookups = 0;
  69. X
  70. Xtime_t cache_lookup(struct tm *tm)
  71. X{
  72. X  cache_t *gaze, *save = 0;
  73. X
  74. X  for (gaze = mru_cache; gaze; save = gaze, gaze = gaze->next) {
  75. X    if (gaze->tment.tm_mday == tm->tm_mday &&
  76. X    gaze->tment.tm_mon  == tm->tm_mon  &&
  77. X    gaze->tment.tm_year == tm->tm_year) {
  78. X      if (gaze != mru_cache) {
  79. X    save->next = gaze->next;
  80. X    gaze->next = mru_cache;
  81. X    mru_cache = gaze;
  82. X      }
  83. X      hits++;
  84. X      return gaze->secs;
  85. X    }
  86. X  }
  87. X  misses++;
  88. X  return 0;
  89. X}
  90. X
  91. Xtime_t caching_mktime(struct tm *tm)
  92. X{
  93. X  struct tm midnight;
  94. X  time_t retv;
  95. X
  96. X  lookups++;
  97. X  midnight = *tm;
  98. X  midnight.tm_sec = midnight.tm_min = midnight.tm_hour = 0;
  99. X  if ((retv = cache_lookup(&midnight)) == 0) {
  100. X    cache_t *cache_ent;
  101. X
  102. X    if ((cache_ent = malloc(sizeof(cache_t))) == 0) {
  103. X      fprintf(stderr, "Out of memory\n");
  104. X      exit(EX_OSERR);
  105. X    }
  106. X    retv = mktime(&midnight);
  107. X    cache_ent->tment = *tm;
  108. X    cache_ent->secs = retv;
  109. X    cache_ent->next = mru_cache;
  110. X    mru_cache = cache_ent;
  111. X  }
  112. X  return retv + tm->tm_hour * HOUR + tm->tm_min * MINUTE + tm->tm_sec;
  113. X}
  114. X
  115. Xvoid cache_stats(void)
  116. X{
  117. X  printf("Caching mktime stats: %d lookups, %d hits, %d misses\n",
  118. X     lookups, hits, misses);
  119. X}
  120. X
  121. END-of-mktime.c
  122. exit
  123.  
  124.