Gperf详解

一、Gperf简介

Gperf是一款代码生成工具，用于生成key-value对的散列表并以C或C++的形式输出。它使用了一种名为“字典树”（trie-tree）的数据结构，并在其基础上进行了优化和改进。采用gperf可以快速生成高效的哈希表。

相比于其他哈希算法，gperf的散列表具有更快的查找速度以及更低的冲突率。在处理大规模数据时，gperf具有优越的性能表现。同时，通过使用gperf的工具，我们可以生成一份清晰且易于阅读的C/C++代码，并且还能够自定义哈希函数。

二、Gperf工具结构

Gperf的工具结构非常简单，我们可以先手动创建一份包含key-value对的输入文件，然后使用gperf工具进行处理，生成源代码文件。

下面以一个简单的例子来展示gperf工具的使用：

%{
#include <stdio.h>
#include <stdlib.h>
%}

struct keyword {
    char *name;
    int type;
};

%%
if      { return IF; }
else    { return ELSE; }
for     { return FOR; }
while   { return WHILE; }
return  { return RETURN; }
// 前面定义了关键词，下面开始定义一些常量或者一些有特殊意义的符号
"+"       { return ADD; }
"-"       { return SUB; }
"*"       { return MUL; }
"/"       { return DIV; }
"="       { return ASSIGN; }
"("       { return LPARE; }
")"       { return RPARE; }
";"       { return SEMICOLON; }
":"       { return COLON; }
","       { return COMMA; }
.{Text}   { return ID; }
\n        { return 0; }
%%

int main(void) {
    yylex();
    return 0;
}

int yywrap(void) {
    return 1;
}

int yylex(void) {
    int c = getchar();
    if (c == EOF) {
        return 0;
    }
    if (c >= 'a' && c <= 'z') {
        char id[100];
        int i = 0;
        do {
            id[i++] = c;
            c = getchar();
        } while (c >= 'a' && c <= 'z');
        ungetc(c, stdin);
        id[i] = '\0';

        struct keyword *p = lookup(id);
        if (p) {
            printf("%d ", p->type);
        } else {
            printf("%d ", ID);
        }
    } else {
        printf("%c ", c);
    }
    return yylex();
}

char *strdup(const char *);

#define NHASH  9997
#define MULTIPLIER  31

struct keyword *lookup(char *s) {
    static struct keyword keywords[] = {
        {"if", IF},
        {"else", ELSE},
        {"for", FOR},
        {"while", WHILE},
        {"return", RETURN},
        {0, 0}
    };
    struct keyword *p;
    char *t;
    unsigned int h = 0;

    for (t = s; *t; t++) {
        h = MULTIPLIER * h + *t;
    }

    h %= NHASH;

    for (p = &keywords[h]; p->name; p++) {
        if (!strcmp(p->name, s)) {
            return p;
        }
    }

    p->name = strdup(s);
    p->type = ID;
    return p;
}

char *strdup(const char *s) {
    char *p;
    p = (char *) malloc(strlen(s) + 1);
    if (p != NULL) {
        strcpy(p, s);
    }
    return p;
}

在上述代码中，我们定义了一个简单的语法分析器，它可以对包含关键词、运算符和标识符等符号的输入文件进行分析，并按照一定规则输出结果。这里我们引入了gperf工具，使用下面的命令处理上述输入文件：

gperf -L ANSI-C -t -E --enum yykey -k "*" -N keyword input.gperf

根据上述命令生成的代码中，会包含一个叫做lookup()的函数，它返回输入值对应的数据结构。下面是生成的C代码：

struct keyword { char *name; int type; };

#define TOTAL_KEYWORDS 5
#define MIN_WORD_LENGTH 2
#define MAX_WORD_LENGTH 6
#define MIN_HASH_VALUE 2
#define MAX_HASH_VALUE 11
/* maximum key range = 10, duplicates = 0 */
#ifdef __GNUC__
__inline
#else
#ifdef __cplusplus
inline
#endif
#endif
static unsigned int
hash (register const char *str, register unsigned int len)
{
  static unsigned short asso_values[] =
    {
      1, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0
    };
  return len + asso_values[(unsigned char)str[0]];
}

struct keyword *
in_word_set (register const char *str, register unsigned int len)
{
  static struct keyword wordlist[] =
    {
      {"for",          1},
      {"else",         2},
      {"while",        3},
      {"if",           4},
      {"return",       5},
      {""}, {""},
      {"",0}
    };

  if (len <= MAX_WORD_LENGTH && len >= MIN_WORD_LENGTH)
    {
      register int key = hash (str, len);

      if (key <= MAX_HASH_VALUE && key >= MIN_HASH_VALUE)
        {
          register const char *s = wordlist[key].name;

          if (*str == *s && !strcmp (str + 1, s + 1))
            return &wordlist[key];
        }
    }
  return 0;
}

这段代码实现了一个哈希表，并提供了一个快速查找的函数in_word_set()。我们可以使用这个函数来查找输入的key是否在哈希表中，并返回对应的value值。

三、gperf性能分析

3.1 gperftools内存分析

gperftools是一套开源的性能分析工具集，其中包括了一些常用的工具，例如CPU性能分析、内存分析、堆栈跟踪等等。其中，内存分析工具heapcheck可以用于检查程序在运行时的内存分配情况，减少内存泄漏和内存溢出等问题。下面我们以一个简单的例子来演示heapcheck的使用方法：

#include <stdio.h>
#include <stdlib.h>
#include <gperftools/heap-checker.h>

void * LeakyFunction(int leakCount) {
  void **memory = (void **) malloc(sizeof(void *) * leakCount);
  for (int i = 0; i < leakCount; i++) {
    memory[i] = (void *) malloc(1024 * 1024);
  }
  return memory;
}

int main(int argc, char *argv[]) {
  int leakCount = 100;
  HeapLeakChecker checker("basic");
  void *memory = LeakyFunction(leakCount);
  checker.ExpectLeaks(leakCount);
  free(memory);
  checker.NoLeaks();
  return 0;
}

通过将gperftools的头文件包含在代码中，并在主函数中添加HeapLeakChecker的实例，我们可以对这个程序进行内存分配的检查。上述例子中，我们定义了一个函数LeakyFunction()，它会分配100个1MB大小的内存块。通过HeapLeakChecker的ExpectLeaks()可以检查我们期望的内存泄漏数目，并通过NoLeaks()方法来检查程序是否发生了内存泄漏。

3.2 gperformance性能分析

gperftools还包含另一个称为gperformance的性能分析工具，它是一款延迟分析工具，可以对函数调用的延迟进行采样和统计。使用gperformance需要先对代码进行编译，然后在启动时加入--gperf-start、--gperf-stop等参数。下面我们以一个简单的例子来演示gperformance的使用方法：

#include <gperftools/profiler.h>
#include <stdlib.h>
#include <unistd.h>

void InnerFunction()
{
  usleep(100);
}

void OutterFunction()
{
  usleep(200);
  InnerFunction();
}

int main(int argc, char **argv)
{
  ProfilerStart("/tmp/prof-example.profile");
  for (int i = 0; i < 100000; i++) {
    OutterFunction();
  }
  ProfilerStop();
  return 0;
}

在上述代码中，我们在开始时调用了ProfilerStart()函数，并指定了统计结果输出到的文件名，然后循环调用了100000次OutterFunction()，每次调用时OutterFunction都会调用InnerFunction()。程序运行结束后，gperformance会自动生成一个性能报告，并在报告中展示各个函数的耗时占比。

四、Gperf特点及应用场景

Gperf具有以下四个特点：

1、性能优秀：使用gperf生成的哈希表具有更快的查找速度以及更低的冲突率。

2、代码简洁：gperf可以生成一份清晰且易于阅读的C/C++代码，并且还能够自定义哈希函数。

3、易于使用：使用gperf可以快速生成高效的哈希表。

4、可靠性高：gperf已经经过了广泛的测试和验证，在处理大规模数据时具有优越的性能表现。

gperf主要应用于大规模数据的快速查找、编译器的语法分析、关键词查找等场景。例如，我们可以在编译器中使用gperf来生成一份自定义的语法分析表，从而提高编译器的语法检查效率。