Advertisement
Guest User

db/profiler.c

a guest
Nov 14th, 2018
160
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 17.64 KB | None | 0 0
  1. //==== NOTE ==================================================================
  2. // You do not need to change anything in this file, but feel free to read it
  3. // if it is of interest.
  4. //
  5. // You only need to update bstdb.c
  6. //============================================================================
  7. #include "profiler.h"
  8.  
  9.  
  10. #define M_PI 3.14159265358979323846
  11. #include <math.h>
  12. #include <time.h>
  13. #include <errno.h>
  14. #include <stdio.h>
  15. #include <string.h>
  16. #include <stdlib.h>
  17.  
  18. #ifdef _WIN32
  19. #include <windows.h>
  20. #endif
  21.  
  22. #ifdef __MACH__
  23. #include <sys/time.h>
  24. #include <mach/clock.h>
  25. #include <mach/mach.h>
  26. #endif
  27.  
  28. #define MU_COLLECTION    100000.0f // average collection size
  29. #define SIGMA_COLLECTION   5000.0f // standard deviation of collection size
  30.  
  31. #define MU_BOOK           10000.0f // average word count of book
  32. #define SIGMA_BOOK          500.0f // standard deviation of book word count
  33.  
  34. #define LONG_STRING 64 // Maximum size of buffer allocated to book title
  35.  
  36. //----------------------------------------------------------------------------
  37. // Book title generation method blatantly stolen from:
  38. // http://novelistvmd.awardspace.com/WesternTitleGenerator2.htm
  39. //
  40. // Essentially we choose random adjectives and random nouns from the two
  41. // arrays below. These are combined according to one of 8 randomly chosen
  42. // title patterns
  43. //
  44. //  1. <ADJECTIVE> <NOUN>
  45. //  2. The <ADJECTIVE> <NOUN>
  46. //  3. <NOUN> of <NOUN>
  47. //  4. The <NOUN>'s <NOUN>
  48. //  5. The <NOUN> of the <NOUN>
  49. //  6. The <NOUN> in the <NOUN>
  50. //  7. The <NOUN> of the <ADJECTIVE> <NOUN>
  51. //  8. The <NOUN> and the <NOUN>
  52. //----------------------------------------------------------------------------
  53.  
  54. static char *nouns[] = {
  55.     "Cowboy","Dream","Dreamer","Settlers","Gunslingers","Maverick","Skies",
  56.     "Class","Sheriff","Desert","Arms","Beauty","Redhead","Gaslight",
  57.     "Lover","Ruby","Widow","Mine","Hope","Bluff","Plains","Lariat","Sierra",
  58.     "Antelope","Prairie","Horizon","Graveyard","Churchyard","Hawk","Landowner",
  59.     "Soul","Souls","Touch","Meadow","Boots","Spurs","Saddle","Gold","Clouds",
  60.     "Men","Women","Mountains","Guitar","Smoke","Cattle","Drive","Stirrup",
  61.     "Ice","Snow","Night","Silk","Secret","Secrets","Dove","Coyote","Wagon",
  62.     "Solitude","Husband","Wife","Man","Woman","Boy","Loner","Wagons","Land",
  63.     "Girl","Raven","Truth","Soldier","Beau","Eagle","Sierras","Outlaw",
  64.     "Body","Captive","Evening","Velvet","Lash","Deer","Rustlers","Leather",
  65.     "Teacher","Lake","Lawman","Temptation","Wolves","Spinet","Drums",
  66.     "Rein","Rainbow","Rain","Flight","Flying","Lark","Dust","Sun","Gun",
  67.     "Soaring","Stallion","Wings","Mist","Sky","Wind","Race","Vultures",
  68.     "Seeker","Winter","River","Door","Mountain","Magic","Yucca","Brook",
  69.     "Honor","Gate","Cloud","Glen","Duster","End","Beginning","Feather",
  70.     "Tale","Waltz","Tales","Steer","Church","Fences","Gentleman","Lady",
  71.     "Vine","Path","Willow","Birch","Birches","Trail","Petals","Destiny",
  72.     "Pine","Garden","Theft","Thief","Legend","Rifle","Squaw","Arapahoe",
  73.     "Chance","Oak","Spark","Sparks","Stream","Streams","Mare","Canoe","Wolf",
  74.     "Bible","Darkness","Silence","Kiss","Book","Butterfly","Death","Sioux",
  75.     "Shadow","Ring","Diary","Storm","Storms","Bullets","Holster","Winchester",
  76.     "Necklace","Stranger","Lord","Lords","Navajo","Tumbleweed","Barrel",
  77.     "Star","Locket","Stars","Painting","Heart","Heat","Cougar","Bandit",
  78.     "Sketch","Twilight","Moon","Shores","Paint","Pinto","Bullet","Calf","Town",
  79.     "Frame","Courage","Doctor","School","Rose","Apache","Spinster",
  80.     "Roses","Stone","Stones","Panel","Creek","Pass","Badlands","Butte","Lamp",
  81.     "Tree","Rattlesnake","Rancher","Tracks","Buffalo","Spring","Autumn","Colt",
  82.     "Spirit","Return","Father","Mother","Brave","Savage","Summer","Winter",
  83.     "Dog","Legacy","Birth","Healer","Healing","Year","Years","Death","Dying",
  84.     "Fall","Lace","Luck","Pearl","Treasure","Tears","Son","Sons","Child",
  85.     "Children","Riders","Destruction","Devotion","Promise","Gift","Word",
  86.     "Stable","Barn","Renegade","Words","Thought","Thoughts","Guard","Angel",
  87.     "Angels","Search","Eye","Lamplight","Eyes","Danger","Game","Fire","Flame",
  88.     "Flames","Bride","Time","Spaniard","Light","Lights","Doors","Window",
  89.     "Windows","Circus","Road","Sombrero","Dirt","Ashes","Memory","Thorn",
  90.     "Thorns","Name","Names","Dozen","Senorita","Sage","Future","Past",
  91.     "Nothing","Arroyo","Gulch","Mesa","Medicine","Map","Bible","Way","Lily",
  92.     "Valley","Abyss","Hunter","Basin","Roundup","Canyon","Edge","Smile",
  93.     "Embrace","Diamond","Grave"
  94. };
  95.  
  96. static char *adjectives[] = {
  97.     "Lost","Only","Last","First","Untamed","Fearless","Third","Sacred",
  98.     "Bold","Lovely","Iron","Fourth","Missing","Shadowy","Seventh","Towering",
  99.     "Unabashed","Unloved","Flaming","Fifth","Vacant","Lace",
  100.     "Cold","Hot","Golden","Enthralled","Lone","Silent","Solitary","Unknown",
  101.     "Sixth","Brave","Whispering","Smooth","Fiery","Enchanted","Silken",
  102.     "Rough","Frozen","Wild","Moonlit","Slender","Trembling","Fallen","Lacey",
  103.     "Ragged","Burned","Splintered","Silk","Distant","Reluctant","Haunted",
  104.     "Magnificent","Luscious","Sparkling","Raven","White","Hurried","Ancient",
  105.     "Hidden","Jeweled","Pastel","Captured","Stolen","Miraculous","Lilac",
  106.     "Cloudy","Unbound","Growing","Kissing","Verdant","Red","Azure",
  107.     "Rising","Falling","Elemental","Unfinished","Bound","Prized","Dungeon",
  108.     "Obsessed","Unwilling","Dancing","Hard","Eager","Ravaged","Sleeping",
  109.     "Mysterious","Proud","Wanton","Professional","Willing","Devoted",
  110.     "Auburn","Misty","Irresistible","Locked","Secluded","Ruby","Final",
  111.     "Missing","Plaintive","Dark","Darkest","Silver","Silvery","Living",
  112.     "Yearning","Black","White","Entwined","Invisible","Legato","Next",
  113.     "Seventh","Scarlet","Green","Blue","Poignant","Violet","Grey","Wounded",
  114.     "Bloody","Emerald","Crystal","Lyrical","Sharp","Delicious","Shattered",
  115.     "Dangerous","Somber","Deep","Twinkling","Dwindling","Absent","Soft",
  116.     "Fierce","Vacant","Burning","Summer","Loneliest","Some","No","All",
  117.     "Tinkling","Grave","Engraved","Living","Dead","Happiest","Echoing",
  118.     "Every","Each","Which","What","Playful","Slumbering","Weeping","Softer",
  119.     "Dying","Lonely","Laughing","Whispering","Forgotten","Empty","Frozen",
  120.     "Magical","Unlucky","Lucky","New","Tentative","Clear","Faraway","Sweet",
  121.     "Hungry","Autumn","Spring","Winter","Broken","Searching","Fleeting",
  122.     "Spellbound"
  123. };
  124.  
  125.  
  126. struct book {
  127.     char title[LONG_STRING]; // Randomly generated book title
  128.     int word_count;          // Randomly generated book length in words
  129.     int db_id;               // Book's assigned ID in the database
  130. };
  131.  
  132. static struct book *g_books = NULL; // We'll make a random number of books
  133. static size_t       g_collection_size = 0; // Number of books created
  134.  
  135. double
  136. get_time ( void ) {
  137. #ifdef _WIN32
  138.     LARGE_INTEGER time;
  139.     LARGE_INTEGER frequency;
  140.  
  141.     QueryPerformanceFrequency(&frequency);
  142.     QueryPerformanceCounter(&time);
  143.  
  144.     return ((double)time.QuadPart) / frequency.QuadPart;
  145. #else
  146.     struct timespec t;
  147. #if __MACH__
  148.     clock_serv_t cclock;
  149.     mach_timespec_t mts;
  150.     host_get_clock_service(mach_host_self(), CALENDAR_CLOCK, &cclock);
  151.     int r = clock_get_time(cclock, &mts);
  152.     mach_port_deallocate(mach_task_self(), cclock);
  153.     t.tv_sec = mts.tv_sec;
  154.     t.tv_nsec = mts.tv_nsec;
  155. #else
  156.     static double prev_value = 0.0;
  157.  
  158.     // CLOCK_MONOTONIC represents the absolute elapsed wall-clock time since
  159.     // some arbitrary, fixed point in the past. It isn't affected by changes in
  160.     // the system time-of-day clock.
  161.     int r = clock_gettime( CLOCK_MONOTONIC, &t );
  162. #endif
  163.     if ( r < 0 ) {
  164.         // gettime can fail, so we need to do a check and possibly print error
  165.         fprintf(stderr, "%s\n", strerror(errno));
  166.         // On error return previous time
  167.         return prev_value;
  168.     }
  169.     double ns = t.tv_nsec;        // get elapsed nanoseconds
  170.     double s = ns * 0.000000001;  // nanoseconds to seconds
  171.     time_t tts = t.tv_sec;        // get elapsed seconds
  172.     s += difftime( tts, 0 );      // count seconds since epoch and add to total
  173.     prev_value = s;               // backup in case future call fails
  174.     return s;                     // return time
  175. #endif
  176. }
  177.  
  178. //=== FUNCTION ================================================================
  179. //         Name: box_muller
  180. //  Description: Uses the Box-Muller transform to generate pseudorandom values
  181. //               according to a Gaussian distribution as determined by the
  182. //               values of mu and sigma.
  183. //
  184. //               The rand() function returns random values according to a
  185. //               uniform distribution. This is fine if we want to give the
  186. //               impression of true randomness. Box-Muller lets us generate
  187. //               random numbers which are clustered around some average value
  188. //               (mu) with a spread that is determined by sigma.
  189. //=============================================================================
  190. static double
  191. box_muller ( double mu, double sigma ) {
  192.     static int gen = 0;
  193.     static double z0, z1;
  194.     double a, r;
  195.  
  196.     // we need to generate two values on every alternating call
  197.     // flip the boolean so we know whether or not to generate
  198.     gen = !gen;
  199.  
  200.     // check to see if we still have a value in reserve.
  201.     if(!gen) {
  202.         // if so, return it
  203.         return z1 * sigma + mu;
  204.     }
  205.  
  206.     // get the angle and radius we'll use to generate the new random values
  207.     a = 2 * M_PI * (rand()/(double)RAND_MAX);
  208.     r = sqrt(-2 * log(rand()/(double)RAND_MAX));
  209.  
  210.     // generate two new Gaussian distributed values from sides of triangle
  211.     z0 = r*cos(a);
  212.     z1 = r*sin(a);
  213.  
  214.     // return one of the two values
  215.     return z0 * sigma + mu;
  216. }
  217.  
  218. //=== FUNCTION ================================================================
  219. //         Name: welford
  220. //  Description: Welford's online algorithm lets us compute a running value
  221. //               for average and variance without needing to store all sample
  222. //               values in memory. With each new value that is generated, we
  223. //               simply update mean and variance in response and then discard
  224. //               the value. Useful for saving space.
  225. //=============================================================================
  226. static void
  227. welford ( double val, size_t i, double *avg, double *var ) {
  228.     double d1, d2, mu=*avg, sig=*var;
  229.  
  230.     d1 = val - mu;
  231.     mu += d1/(i+1);
  232.     d2 = val - mu;
  233.     sig += d1*d2;
  234.  
  235.     *avg = mu;
  236.     *var = sig;
  237. }
  238.  
  239. //=== FUNCTION ================================================================
  240. //         Name: generate_book
  241. //  Description: Generate a book with a random title and length.
  242. //=============================================================================
  243. static void
  244. generate_book ( struct book *book ) {
  245.     static size_t num_nouns  = sizeof(nouns)/sizeof(nouns[0]);
  246.     static size_t num_adj   = sizeof(adjectives)/sizeof(adjectives[0]);
  247.  
  248.     // Book length is derived from normal distribution
  249.     book->word_count = box_muller( MU_BOOK, SIGMA_BOOK );
  250.  
  251.     // Pick random title pattern, then pick random title nouns/adjectives
  252.     switch (rand()%8) {
  253.         case 0:
  254.             sprintf( book->title, "%s %s",
  255.                 adjectives[rand()%num_adj], nouns[rand()%num_nouns]);
  256.             break;
  257.         case 1:
  258.             sprintf( book->title, "The %s %s",
  259.                 adjectives[rand()%num_adj], nouns[rand()%num_nouns]);
  260.             break;
  261.         case 2:
  262.             sprintf( book->title, "%s of %s",
  263.                 nouns[rand()%num_nouns], nouns[rand()%num_nouns]);
  264.             break;
  265.         case 3:
  266.             sprintf( book->title, "The %s's %s",
  267.                 nouns[rand()%num_nouns], nouns[rand()%num_nouns]);
  268.             break;
  269.         case 4:
  270.             sprintf( book->title, "The %s of the %s",
  271.                 nouns[rand()%num_nouns], nouns[rand()%num_nouns]);
  272.             break;
  273.         case 5:
  274.             sprintf( book->title, "%s in the %s",
  275.                 nouns[rand()%num_nouns], nouns[rand()%num_nouns]);
  276.             break;
  277.         case 6:
  278.             sprintf( book->title, "The %s of the %s %s",
  279.                 nouns[rand()%num_nouns], adjectives[rand()%num_adj],
  280.                 nouns[rand()%num_nouns]);
  281.             break;
  282.         case 7:
  283.         default:
  284.             // If something goes wrong, just default to the eigth pattern
  285.             sprintf( book->title, "The %s and the %s",
  286.                 nouns[rand()%num_nouns], nouns[rand()%num_nouns]);
  287.             break;
  288.     }
  289. }
  290.  
  291. //=== FUNCTION ================================================================
  292. //         Name: insertion
  293. //  Description: Perform an insertion using profiler's database. Return 0 if
  294. //               no error occurred and 1 if something went wrong
  295. //=============================================================================
  296. static int
  297. insertion ( struct profile *p, int i ) {
  298.     g_books[i].db_id = p->db->add( g_books[i].title, g_books[i].word_count );
  299.     return ( g_books[i].db_id < 0 );
  300. }
  301.  
  302. //=== FUNCTION ================================================================
  303. //         Name: search_title
  304. //  Description: Perform random title search using profiler's database.
  305. //               Return 0 if no error occurred and 1 if something went wrong
  306. //=============================================================================
  307. static int
  308. search_title ( struct profile *p, int i ) {
  309.     size_t j = rand()%g_collection_size;
  310.     char *t = p->db->get_name( g_books[j].db_id );
  311.     return ( !t || strcmp( g_books[j].title, t ) != 0 );
  312. }
  313.  
  314. //=== FUNCTION ================================================================
  315. //         Name: search_word_count
  316. //  Description: Perform random word count search using profiler's database.
  317. //               Return 0 if no error occurred and 1 if something went wrong
  318. //=============================================================================
  319. static int
  320. search_word_count ( struct profile *p, int i ) {
  321.     size_t j = rand()%g_collection_size;
  322.     int wc = p->db->get_word_count( g_books[j].db_id );
  323.     return ( wc < 0 || wc != g_books[j].word_count );
  324. }
  325.  
  326. //=== FUNCTION ================================================================
  327. //         Name: profile_timed_op
  328. //  Description: Repeatedly performs one of the three operations defined above
  329. //               and maintains values for average execution time, number of
  330. //               errors, etc.
  331. //=============================================================================
  332. static void
  333. profile_timed_op ( struct profile *p, int (*op)(struct profile *p, int i),
  334.         double *total_time, double *avg_time, double *var_time, int *errors,
  335.         int *total_ops, size_t iterations ) {
  336.     double start, end, t1, t2;
  337.  
  338.     *avg_time = *var_time = *errors = 0;
  339.  
  340.     start = get_time();
  341.     for ( *total_ops=0; *total_ops<iterations; (*total_ops)++ ) {
  342.         t1 = get_time();
  343.         *errors += op(p,*total_ops);
  344.         t2 = get_time();
  345.         // welford's algorithm for computing running variance and average
  346.         welford ( t2-t1, *total_ops, avg_time, var_time );
  347.     }
  348.     end = get_time();
  349.     *total_time = end-start;
  350. }
  351.  
  352. //=== FUNCTION ================================================================
  353. //         Name: profiler_init
  354. //  Description: Initialize any global data that is required by the profiler
  355. //=============================================================================
  356. int
  357. profiler_init ( void ) {
  358.     srand(time(NULL));
  359.  
  360.     // Generate our random collection of books. Make the size of the collection
  361.     // too, just so we aren't tempted to solve for only one collection size.
  362.     g_collection_size = box_muller( MU_COLLECTION, SIGMA_COLLECTION );
  363.     g_books = malloc( sizeof(struct book)*g_collection_size );
  364.     if (!g_books) {
  365.         return 0;
  366.     }
  367.  
  368.     printf("Generating %lu books... ", g_collection_size);
  369.     fflush(stdout);
  370.     for ( size_t i=0; i<g_collection_size; i++ ) {
  371.         generate_book( &g_books[i] );
  372.     }
  373.     printf("OK\n");
  374.  
  375.     return 1;
  376. }
  377.  
  378. //=== FUNCTION ================================================================
  379. //         Name: profiler_run
  380. //  Description: Profile a database
  381. //=============================================================================
  382. void
  383. profiler_run ( struct profile *p ) {
  384.     // profile insertion time
  385.     profile_timed_op(
  386.         p,
  387.         insertion,
  388.         &p->total_insert_time,
  389.         &p->avg_insert_time,
  390.         &p->var_insert_time,
  391.         &p->insert_errors,
  392.         &p->total_insert,
  393.         g_collection_size
  394.     );
  395.  
  396.     // profile title search time across 10% of inserted documents
  397.     profile_timed_op(
  398.         p,
  399.         search_title,
  400.         &p->total_search_time_title,
  401.         &p->avg_search_time_title,
  402.         &p->var_search_time_title,
  403.         &p->search_title_errors,
  404.         &p->total_search_title,
  405.         g_collection_size/10
  406.     );
  407.  
  408.     // profile word count search time across 10% of inserted documents
  409.     profile_timed_op(
  410.         p,
  411.         search_word_count,
  412.         &p->total_search_time_word_count,
  413.         &p->avg_search_time_word_count,
  414.         &p->var_search_time_word_count,
  415.         &p->search_word_count_errors,
  416.         &p->total_search_word_count,
  417.         g_collection_size/10
  418.     );
  419. }
  420.  
  421. //=== FUNCTION ================================================================
  422. //         Name: profiler_quit
  423. //  Description: Free any memory that was allocated to the profiler
  424. //=============================================================================
  425. void
  426. profiler_quit ( void ) {
  427.     if (g_books) {
  428.         free(g_books);
  429.     }
  430. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement