This is the mail archive of the mailing list for the binutils project.

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Patricia Trie pseudo-test

OK it took me 2 hours to make this work, and right now I do not want to
deal with figuring out the rest of it because I don't even have my
compsci AAS and have NO algorithms experience so this is brute force
learning and I am learning that debugging algorithms written by
horrible, horrible first-year compsci students is IRRITATING.

........ frustration vented, let's continue.

(yes this message is REALLY ugly, and confusing, sorry.  My thoughts are
unorganized and I don't have enough data for a good argument here YET.)

A while ago I proposed replacing the symbol strings (what section is
that, .dynstr?) with patricia tries instead of hash chains (which as I
understand are just linked lists jammed in a hash bucket) because of
Drepper's paper about DSOs and common prefixes.

Anyway, the gist of the idea is that I'm assuming the current symbol
string structure is as follows:

[Hash Table]--->[Bucket]-->[Symbol foobar]
                        |->[Symbol foobaz]
                        |->[Symbol foogonk]...

I'm looking at instead

[Hash Table]--->[Bucket]-->[Symbol foo]-->[ba]-->[r]
                                       |      |->[z]

Such that when we have common prefixes, at the point where the strings
diverge, we simply have to follow a branch.

I wrote a small test program (attached) that builds a patricia trie and
then dumps it, giving an analysis of the maximum depth (branches taken)
and the longest common prefix.

Well, Drepper's right at least.  libgtk shows 10 branches when I
patricia trie up the symbols, and a maximum common prefix of 35
characters; where with libgtkmm I get 16 branches and the biggest common
prefix it can find is 229 characters.  Landing these in a hash bucket is
wasteful; to beat it I'll need a branch that's less intensive than 3.5
character comparisons... or not.

If we assume there's only 2 entries sharing the common prefix, that's
great.  Except, when we branch, we have AT LEAST two entries sharing
THIS common prefix.  If we branch AGAIN, then we have at least THREE
entries sharing the first prefix, and at least TWO entries sharing the
shorter prefix (at the first branch).  So if we branch TEN TIMES,
there's a prefix shared 10 times, a longer one shared 9 times, a longer
one shared 8 times, ... a longer one shared twice, and then a unique
string.  I have no idea what the implications are though I can guess
there are branches at namespace and class when dealing with C++ symbols.

(the real theoretical minimum is not 35 / 10; it's (1+2+3+4+5+6+7+8+9
+35) / 10 == 80/10 == 8.  It doesn't much matter)

The number of branches is easily reduced by reducing the number of items
in the hash bucket (if there's 5 items, you can only branch in 5 places
and probably won't approach that) and using Patricia Tries in place of
hash chains instead of replacing the whole hash table.  This is probably
a good idea, since the only space-efficient storage methods I can come
up with would be O(n) for n=num_branches operations per branch (each
operation is 1 character comparison*; on top of that is one additional
long addition.)

*(comparing two strings, each character comparison is a compare and a
long addition to iterate in a loop)

So far I do NOT have a way to store this such that the branches are
guaranteed less intensive than 8 character comparisons; and don't have
real numbers on what I need.  I'm still thinking this is probably a win
since we're unlikely to branch 8 times from a common prefix and even if
we do we're suddenly faced with a situation where we CAN assume we're
winning something*; Drepper are you around, I could use your input.

*(every extra direction we can take at a branch represents one more
comparison of however many characters long the prefix is; so if we
branch 8 ways after a prefix of 2 characters, we're spending 8 + 7 + 6 +
5 + 4 + 3 + 2 + 1 to avoid (8 + 7 + 6 + 5 + 4 + 3 + 2 + 1) * 2...
somebody verify this for me, I think I just did something awesome and
that shouldn't be possible)

For those who want to keep trying, my crappy analysis program is
attached.  I used the below command to divine some useful numbers:

readelf -sW /usr/lib/ | tail -n +4 | awk '{print $8}' | grep -v
'^$' | ./ptree 

(In case you haven't noticed yet, I trust my intuitions to fill in where
my technical knowledge is lacking; and then try to find out if anyone
else has something solid for me.

John Moser <>
#include <stdlib.h>
#include <string.h>
#include <stdio.h>

/* Trie structure:
 * |-Child -> Sibling -> Sibling
 *            |-Child -> Sibling -> Sibling
 *            ......
struct patricia {
	char	*text;
	void	*data;
	struct patricia
	struct patricia

struct patricia phead = { "", 0, 0, 0};

int strprefix(const char *s1, const char *s2) {
	int i = 0;
	while(s1[i] == s2[i] && s1[i])
	return i;

static inline struct patricia *new_patricia_node(char *text,
	void *data,
	struct patricia *sibling,
	struct patricia *child) {
	struct patricia *new_node = NULL;

	new_node = malloc(sizeof(struct patricia));
	new_node->text		= text;
	new_node->data		= data;
	new_node->sibling	= sibling;
	new_node->child		= child;

	return new_node;

int add_to_patricia(char *key,
	void *value) {
	struct patricia *node = &phead;
	struct patricia *new_node = NULL;
	int i=0,j=0;
	char *str;

    while(1) {
	j += i;
	i = strprefix(key + j, node->text);

	/* No move, test sibling */
	if (!i) {
		/* No sibling, we're becoming one */
		if (!node->sibling) {
			str = malloc(strlen(key + j + i) + 1);
			strcpy(str, key + j + i);

			new_node = new_patricia_node(str, value, NULL, NULL);
			node->sibling = new_node;
		node = node->sibling;

	/* Holy crap we found this node already! Change value
	 * this is the only time these are equal  */
	if (!key[j + i] && !node->text[i]) { 
		node->data = value;

	/* The node has to be split; we're becoming the parent */
	if (!key[j + i]) {
		/*The end of the node's text becomes our child's text*/
		str = malloc(strlen(node->text + i) + 1);
		strcpy(str, node->text + i);
		/* node's siblings become our siblings;
  		 * but it keeps its children */
		new_node = new_patricia_node(str, node->data, NULL, node->child);

		/*Shrink node->text*/
		node->text[i]	= '\0';
		node->text = realloc(node->text, strlen(node->text) + 1);
		node->data	= value;
		node->child	= new_node;


	/* We completed this node; we'll be a child*/
	if (!node->text[i]) {
		if (!node->child) {
			str = malloc(strlen(key + j + i) + 1);
			strcpy(str, key + j + i);

			new_node = new_patricia_node(str, value, NULL, NULL);
			node->child	  = new_node;

		node = node->child;

	/* We have to split this node and demote both the key and the
	 * node to children */
	if (node->text[i] && key[j + i]) {
		/* First, make this node its own child */
		/* Use the string suffix as the text */
		str = malloc(strlen(node->text + i) + 1);
		strcpy(str, node->text + i);

		/* Also demote the data */
		new_node = new_patricia_node(str, node->data, NULL, NULL);
		node->child	  = new_node;
		node->data	  = NULL;
		/* Truncate the parent string */
		node->text[i]	  = '\0';
		node->text = realloc(node->text, strlen(node->text) + 1);

		node = node->child;

		/* Now insert our key */
		/* Use the string suffix as the text */
		str = malloc(strlen(key + j + i) + 1);
		strcpy(str, key + j + i);

		new_node = new_patricia_node(str, value, NULL, NULL);
		node->sibling	  = new_node;



	return 0;

#if 1
int maxdepth = 0;
int cpxlen = 0;
void ptree_spill(char *s, struct patricia *node, int depth, int len) {
	printf("n:%p t:%s v:%i s:%p c:%p\n"
		"     p:%s d:%i x: %i l:%i\n",
		node->data ? *((int*)node->data) : 0,
		s ? s : "",
		len + strlen(node->text));
	if (depth > maxdepth)
		maxdepth = depth;
	if (len > cpxlen) // common prefix length
		cpxlen = len;
	if (node->child)
		ptree_spill(node->text, node->child, depth+1, len + strlen(node->text));
	if (node->sibling)
		ptree_spill(s, node->sibling, depth, len);

int main() {
	int data = 5;
	int data1 = 12;
	int data2 = 6;
	int data3 = 8;
#if 0
	printf("Insert 1\n");
	add_to_patricia("patricia", &data);
	ptree_spill("", &phead);
	printf("Insert 2\n");
	add_to_patricia("patrikana", &data1);
	ptree_spill("", &phead);
	printf("Insert 3\n");
	add_to_patricia("patriciaworm", &data2);
	ptree_spill("", &phead);
	printf("Insert 4\n");
	add_to_patricia("patriciacool", &data3);
	ptree_spill("", &phead);
  char *line = NULL;
  size_t len = 0;
  ssize_t n;
  int sint=0;
  unsigned int (*hash) (const char *);

  while ((n = getline (&line, &len, stdin)) > 0)
      if (line[n - 1] == '\n')
	line[n - 1] = '\0';
	add_to_patricia(line, &data);
	ptree_spill("", &phead, 0, 0);
	printf("Max depth:  %i\n"
		"Max common prefix length:  %i\n",
		maxdepth, cpxlen);
	return 0;

Attachment: signature.asc
Description: This is a digitally signed message part

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]