ld: 25% faster

The ld time was dominated by symbol table processing, so
  * increase hash table size
  * emit fewer symbols in gc (just 1 per string, 1 per type)
  * add read-only lookup to avoid creating spurious symbols
  * add linked list to speed whole-table traversals

Breaks dwarf generator (no idea why), so disable dwarf.

Reduces time for 6l to link godoc by 25%.

R=ken2
CC=golang-dev
https://golang.org/cl/4383047

20 files changed, 303 insertions, 561 deletions

diff --git a/src/cmd/5g/gobj.c b/src/cmd/5g/gobj.c
index bf59534b9b..acece6c0dd 100644
--- a/src/cmd/5g/gobj.c
+++ b/src/cmd/5g/gobj.c
@@ -268,7 +268,7 @@ static Prog *estrdat;
 static int gflag;
 static Prog *savepc;
 
-static void
+void
 data(void)
 {
 	gflag = debug['g'];
@@ -285,7 +285,7 @@ data(void)
 	pc = estrdat;
 }
 
-static void
+void
 text(void)
 {
 	if(!savepc)
@@ -310,6 +310,29 @@ dumpdata(void)
 	pc = estrdat;
 }
 
+int
+dsname(Sym *sym, int off, char *t, int n)
+{
+	Prog *p;
+
+	p = gins(ADATA, N, N);
+	p->from.type = D_OREG;
+	p->from.name = D_EXTERN;
+	p->from.etype = TINT32;
+	p->from.offset = off;
+	p->from.reg = NREG;
+	p->from.sym = sym;
+	
+	p->reg = n;
+	
+	p->to.type = D_SCONST;
+	p->to.name = D_NONE;
+	p->to.reg = NREG;
+	p->to.offset = 0;
+	memmove(p->to.sval, t, n);
+	return off + n;
+}
+
 /*
  * make a refer to the data s, s+len
  * emitting DATA if needed.
@@ -317,76 +340,15 @@ dumpdata(void)
 void
 datastring(char *s, int len, Addr *a)
 {
-	int w;
-	Prog *p;
-	Addr ac, ao;
-	static int gen;
-	struct {
-		Strlit lit;
-		char buf[100];
-	} tmp;
-
-	// string
-	memset(&ao, 0, sizeof(ao));
-	ao.type = D_OREG;
-	ao.name = D_STATIC;
-	ao.etype = TINT32;
-	ao.offset = 0;		// fill in
-	ao.reg = NREG;
-
-	// constant
-	memset(&ac, 0, sizeof(ac));
-	ac.type = D_CONST;
-	ac.name = D_NONE;
-	ac.offset = 0;		// fill in
-	ac.reg = NREG;
-
-	// huge strings are made static to avoid long names.
-	if(len > 100) {
-		snprint(namebuf, sizeof(namebuf), ".string.%d", gen++);
-		ao.sym = lookup(namebuf);
-		ao.name = D_STATIC;
-	} else {
-		if(len > 0 && s[len-1] == '\0')
-			len--;
-		tmp.lit.len = len;
-		memmove(tmp.lit.s, s, len);
-		tmp.lit.s[len] = '\0';
-		len++;
-		snprint(namebuf, sizeof(namebuf), "\"%Z\"", &tmp.lit);
-		ao.sym = pkglookup(namebuf, stringpkg);
-		ao.name = D_EXTERN;
-	}
-	*a = ao;
-
-	// only generate data the first time.
-	if(ao.sym->flags & SymUniq)
-		return;
-	ao.sym->flags |= SymUniq;
-
-	data();
-	for(w=0; w<len; w+=8) {
-		p = pc;
-		gins(ADATA, N, N);
-
-		// DATA s+w, [NSNAME], $"xxx"
-		p->from = ao;
-		p->from.offset = w;
-
-		p->reg = NSNAME;
-		if(w+8 > len)
-			p->reg = len-w;
-
-		p->to = ac;
-		p->to.type = D_SCONST;
-		p->to.offset = len;
-		memmove(p->to.sval, s+w, p->reg);
-	}
-	p = pc;
-	ggloblsym(ao.sym, len, ao.name == D_EXTERN);
-	if(ao.name == D_STATIC)
-		p->from.name = D_STATIC;
-	text();
+	Sym *sym;
+	
+	sym = stringsym(s, len);
+	a->type = D_OREG;
+	a->name = D_EXTERN;
+	a->etype = TINT32;
+	a->offset = widthptr+4;  // skip header
+	a->reg = NREG;
+	a->sym = sym;
 }
 
 /*
@@ -396,77 +358,15 @@ datastring(char *s, int len, Addr *a)
 void
 datagostring(Strlit *sval, Addr *a)
 {
-	Prog *p;
-	Addr ac, ao, ap;
-	int32 wi, wp;
-	static int gen;
-
-	memset(&ac, 0, sizeof(ac));
-	memset(&ao, 0, sizeof(ao));
-	memset(&ap, 0, sizeof(ap));
-
-	// constant
-	ac.type = D_CONST;
-	ac.name = D_NONE;
-	ac.offset = 0;			// fill in
-	ac.reg = NREG;
-
-	// string len+ptr
-	ao.type = D_OREG;
-	ao.name = D_STATIC;		// fill in
-	ao.etype = TINT32;
-	ao.sym = nil;			// fill in
-	ao.reg = NREG;
-
-	// $string len+ptr
-	datastring(sval->s, sval->len, &ap);
-	ap.type = D_CONST;
-	ap.etype = TINT32;
-
-	wi = types[TUINT32]->width;
-	wp = types[tptr]->width;
-
-	if(ap.name == D_STATIC) {
-		// huge strings are made static to avoid long names
-		snprint(namebuf, sizeof(namebuf), ".gostring.%d", ++gen);
-		ao.sym = lookup(namebuf);
-		ao.name = D_STATIC;
-	} else {
-		// small strings get named by their contents,
-		// so that multiple modules using the same string
-		// can share it.
-		snprint(namebuf, sizeof(namebuf), "\"%Z\"", sval);
-		ao.sym = pkglookup(namebuf, gostringpkg);
-		ao.name = D_EXTERN;
-	}
-
-	*a = ao;
-	if(ao.sym->flags & SymUniq)
-		return;
-	ao.sym->flags |= SymUniq;
-
-	data();
-	// DATA gostring, wp, $cstring
-	p = pc;
-	gins(ADATA, N, N);
-	p->from = ao;
-	p->reg = wp;
-	p->to = ap;
-
-	// DATA gostring+wp, wi, $len
-	p = pc;
-	gins(ADATA, N, N);
-	p->from = ao;
-	p->from.offset = wp;
-	p->reg = wi;
-	p->to = ac;
-	p->to.offset = sval->len;
-
-	p = pc;
-	ggloblsym(ao.sym, types[TSTRING]->width, ao.name == D_EXTERN);
-	if(ao.name == D_STATIC)
-		p->from.name = D_STATIC;
-	text();
+	Sym *sym;
+	
+	sym = stringsym(sval->s, sval->len);
+	a->type = D_OREG;
+	a->name = D_EXTERN;
+	a->etype = TINT32;
+	a->offset = 0;  // header
+	a->reg = NREG;
+	a->sym = sym;
 }
 
 void
diff --git a/src/cmd/5l/l.h b/src/cmd/5l/l.h
index 9ce9d02c6c..cf5a9990b9 100644
--- a/src/cmd/5l/l.h
+++ b/src/cmd/5l/l.h
@@ -148,6 +148,7 @@ struct	Sym
 	uchar	foreign;	// called by arm if thumb, by thumb if arm
 	uchar	fnptr;	// used as fn ptr
 	Sym*	hash;	// in hash table
+	Sym*	allsym;	// in all symbol list
 	Sym*	next;	// in text or data list
 	Sym*	sub;	// in SSUB list
 	Sym*	outer;	// container of sub
@@ -265,7 +266,6 @@ enum
 	LEAF		= 1<<2,
 
 	STRINGSZ	= 200,
-	NHASH		= 10007,
 	MINSIZ		= 64,
 	NENT		= 100,
 	MAXIO		= 8192,
diff --git a/src/cmd/6g/gobj.c b/src/cmd/6g/gobj.c
index b667ae48a2..507764a3bc 100644
--- a/src/cmd/6g/gobj.c
+++ b/src/cmd/6g/gobj.c
@@ -280,7 +280,7 @@ static Prog *estrdat;
 static int gflag;
 static Prog *savepc;
 
-static void
+void
 data(void)
 {
 	gflag = debug['g'];
@@ -297,7 +297,7 @@ data(void)
 	pc = estrdat;
 }
 
-static void
+void
 text(void)
 {
 	if(!savepc)
@@ -322,6 +322,24 @@ dumpdata(void)
 	pc = estrdat;
 }
 
+int
+dsname(Sym *s, int off, char *t, int n)
+{
+	Prog *p;
+
+	p = gins(ADATA, N, N);
+	p->from.type = D_EXTERN;
+	p->from.index = D_NONE;
+	p->from.offset = off;
+	p->from.scale = n;
+	p->from.sym = s;
+	
+	p->to.type = D_SCONST;
+	p->to.index = D_NONE;
+	memmove(p->to.sval, t, n);
+	return off + n;
+}
+
 /*
  * make a refer to the data s, s+len
  * emitting DATA if needed.
@@ -329,74 +347,13 @@ dumpdata(void)
 void
 datastring(char *s, int len, Addr *a)
 {
-	int w;
-	Prog *p;
-	Addr ac, ao;
-	static int gen;
-	struct {
-		Strlit lit;
-		char buf[100];
-	} tmp;
-
-	// string
-	memset(&ao, 0, sizeof(ao));
-	ao.type = D_STATIC;
-	ao.index = D_NONE;
-	ao.etype = TINT32;
-	ao.offset = 0;		// fill in
-
-	// constant
-	memset(&ac, 0, sizeof(ac));
-	ac.type = D_CONST;
-	ac.index = D_NONE;
-	ac.offset = 0;		// fill in
-
-	// huge strings are made static to avoid long names.
-	if(len > 100) {
-		snprint(namebuf, sizeof(namebuf), ".string.%d", gen++);
-		ao.sym = lookup(namebuf);
-		ao.type = D_STATIC;
-	} else {
-		if(len > 0 && s[len-1] == '\0')
-			len--;
-		tmp.lit.len = len;
-		memmove(tmp.lit.s, s, len);
-		tmp.lit.s[len] = '\0';
-		len++;
-		snprint(namebuf, sizeof(namebuf), "\"%Z\"", &tmp.lit);
-		ao.sym = pkglookup(namebuf, stringpkg);
-		ao.type = D_EXTERN;
-	}
-	*a = ao;
-
-	// only generate data the first time.
-	if(ao.sym->flags & SymUniq)
-		return;
-	ao.sym->flags |= SymUniq;
-
-	data();
-	for(w=0; w<len; w+=8) {
-		p = pc;
-		gins(ADATA, N, N);
-
-		// DATA s+w, [NSNAME], $"xxx"
-		p->from = ao;
-		p->from.offset = w;
-
-		p->from.scale = NSNAME;
-		if(w+8 > len)
-			p->from.scale = len-w;
-
-		p->to = ac;
-		p->to.type = D_SCONST;
-		p->to.offset = len;
-		memmove(p->to.sval, s+w, p->from.scale);
-	}
-	p = pc;
-	ggloblsym(ao.sym, len, ao.type == D_EXTERN);
-	if(ao.type == D_STATIC)
-		p->from.type = D_STATIC;
-	text();
+	Sym *sym;
+	
+	sym = stringsym(s, len);
+	a->type = D_EXTERN;
+	a->sym = sym;
+	a->offset = widthptr+4;  // skip header
+	a->etype = TINT32;
 }
 
 /*
@@ -406,76 +363,13 @@ datastring(char *s, int len, Addr *a)
 void
 datagostring(Strlit *sval, Addr *a)
 {
-	Prog *p;
-	Addr ac, ao, ap;
-	int32 wi, wp;
-	static int gen;
-
-	memset(&ac, 0, sizeof(ac));
-	memset(&ao, 0, sizeof(ao));
-	memset(&ap, 0, sizeof(ap));
-
-	// constant
-	ac.type = D_CONST;
-	ac.index = D_NONE;
-	ac.offset = 0;			// fill in
-
-	// string len+ptr
-	ao.type = D_STATIC;		// fill in
-	ao.index = D_NONE;
-	ao.etype = TINT32;
-	ao.sym = nil;			// fill in
-
-	// $string len+ptr
-	datastring(sval->s, sval->len, &ap);
-	ap.index = ap.type;
-	ap.type = D_ADDR;
-	ap.etype = TINT32;
-
-	wi = types[TUINT32]->width;
-	wp = types[tptr]->width;
-
-	if(ap.index == D_STATIC) {
-		// huge strings are made static to avoid long names
-		snprint(namebuf, sizeof(namebuf), ".gostring.%d", ++gen);
-		ao.sym = lookup(namebuf);
-		ao.type = D_STATIC;
-	} else {
-		// small strings get named by their contents,
-		// so that multiple modules using the same string
-		// can share it.
-		snprint(namebuf, sizeof(namebuf), "\"%Z\"", sval);
-		ao.sym = pkglookup(namebuf, gostringpkg);
-		ao.type = D_EXTERN;
-	}
-
-	*a = ao;
-	if(ao.sym->flags & SymUniq)
-		return;
-	ao.sym->flags |= SymUniq;
-
-	data();
-	// DATA gostring, wp, $cstring
-	p = pc;
-	gins(ADATA, N, N);
-	p->from = ao;
-	p->from.scale = wp;
-	p->to = ap;
-
-	// DATA gostring+wp, wi, $len
-	p = pc;
-	gins(ADATA, N, N);
-	p->from = ao;
-	p->from.offset = wp;
-	p->from.scale = wi;
-	p->to = ac;
-	p->to.offset = sval->len;
-
-	p = pc;
-	ggloblsym(ao.sym, types[TSTRING]->width, ao.type == D_EXTERN);
-	if(ao.type == D_STATIC)
-		p->from.type = D_STATIC;
-	text();
+	Sym *sym;
+	
+	sym = stringsym(sval->s, sval->len);
+	a->type = D_EXTERN;
+	a->sym = sym;
+	a->offset = 0;  // header
+	a->etype = TINT32;
 }
 
 void
diff --git a/src/cmd/6l/asm.c b/src/cmd/6l/asm.c
index 3e2fe69604..ba2074fde0 100644
--- a/src/cmd/6l/asm.c
+++ b/src/cmd/6l/asm.c
@@ -1101,37 +1101,34 @@ genasmsym(void (*put)(Sym*, char*, int, vlong, vlong, int, Sym*))
 {
 	Auto *a;
 	Sym *s;
-	int h;
 
-	for(h=0; h<NHASH; h++) {
-		for(s=hash[h]; s!=S; s=s->hash) {
-			if(s->hide)
-				continue;
-			switch(s->type&~SSUB) {
-			case SCONST:
-			case SRODATA:
-			case SDATA:
-			case SELFDATA:
-			case SMACHOGOT:
-			case STYPE:
-			case SSTRING:
-			case SGOSTRING:
-			case SWINDOWS:
-				if(!s->reachable)
-					continue;
-				put(s, s->name, 'D', symaddr(s), s->size, s->version, s->gotype);
+	for(s=allsym; s!=S; s=s->allsym) {
+		if(s->hide)
+			continue;
+		switch(s->type&~SSUB) {
+		case SCONST:
+		case SRODATA:
+		case SDATA:
+		case SELFDATA:
+		case SMACHOGOT:
+		case STYPE:
+		case SSTRING:
+		case SGOSTRING:
+		case SWINDOWS:
+			if(!s->reachable)
 				continue;
+			put(s, s->name, 'D', symaddr(s), s->size, s->version, s->gotype);
+			continue;
 
-			case SBSS:
-				if(!s->reachable)
-					continue;
-				put(s, s->name, 'B', symaddr(s), s->size, s->version, s->gotype);
+		case SBSS:
+			if(!s->reachable)
 				continue;
+			put(s, s->name, 'B', symaddr(s), s->size, s->version, s->gotype);
+			continue;
 
-			case SFILE:
-				put(nil, s->name, 'f', s->value, 0, s->version, 0);
-				continue;
-			}
+		case SFILE:
+			put(nil, s->name, 'f', s->value, 0, s->version, 0);
+			continue;
 		}
 	}
 
diff --git a/src/cmd/6l/l.h b/src/cmd/6l/l.h
index 139b06af89..4fc13b94ae 100644
--- a/src/cmd/6l/l.h
+++ b/src/cmd/6l/l.h
@@ -138,6 +138,7 @@ struct	Sym
 	int32	plt;
 	int32	got;
 	Sym*	hash;	// in hash table
+	Sym*	allsym;	// in all symbol list
 	Sym*	next;	// in text or data list
 	Sym*	sub;	// in SSUB list
 	Sym*	outer;	// container of sub
@@ -178,7 +179,6 @@ struct	Movtab
 
 enum
 {
-	NHASH		= 10007,
 	MINSIZ		= 8,
 	STRINGSZ	= 200,
 	MINLC		= 1,
diff --git a/src/cmd/6l/obj.c b/src/cmd/6l/obj.c
index f113e3ec1e..6b43d2df43 100644
--- a/src/cmd/6l/obj.c
+++ b/src/cmd/6l/obj.c
@@ -287,7 +287,7 @@ zsym(char *pn, Biobuf *f, Sym *h[])
 {	
 	int o;
 	
-	o = Bgetc(f);
+	o = BGETC(f);
 	if(o < 0 || o >= NSYM || h[o] == nil)
 		mangle(pn);
 	return h[o];
@@ -301,12 +301,12 @@ zaddr(char *pn, Biobuf *f, Adr *a, Sym *h[])
 	Sym *s;
 	Auto *u;
 
-	t = Bgetc(f);
+	t = BGETC(f);
 	a->index = D_NONE;
 	a->scale = 0;
 	if(t & T_INDEX) {
-		a->index = Bgetc(f);
-		a->scale = Bgetc(f);
+		a->index = BGETC(f);
+		a->scale = BGETC(f);
 	}
 	a->offset = 0;
 	if(t & T_OFFSET) {
@@ -330,7 +330,7 @@ zaddr(char *pn, Biobuf *f, Adr *a, Sym *h[])
 		a->type = D_SCONST;
 	}
 	if(t & T_TYPE)
-		a->type = Bgetc(f);
+		a->type = BGETC(f);
 	if(a->type < 0 || a->type >= D_SIZE)
 		mangle(pn);
 	adrgotype = S;
@@ -405,10 +405,10 @@ newloop:
 loop:
 	if(f->state == Bracteof || Boffset(f) >= eof)
 		goto eof;
-	o = Bgetc(f);
+	o = BGETC(f);
 	if(o == Beof)
 		goto eof;
-	o |= Bgetc(f) << 8;
+	o |= BGETC(f) << 8;
 	if(o <= AXXX || o >= ALAST) {
 		if(o < 0)
 			goto eof;
@@ -421,8 +421,8 @@ loop:
 		sig = 0;
 		if(o == ASIGNAME)
 			sig = Bget4(f);
-		v = Bgetc(f);	/* type */
-		o = Bgetc(f);	/* sym */
+		v = BGETC(f);	/* type */
+		o = BGETC(f);	/* sym */
 		r = 0;
 		if(v == D_STATIC)
 			r = version;
diff --git a/src/cmd/8g/gobj.c b/src/cmd/8g/gobj.c
index e48ad529bf..bc1dfe8bf6 100644
--- a/src/cmd/8g/gobj.c
+++ b/src/cmd/8g/gobj.c
@@ -320,6 +320,24 @@ dumpdata(void)
 	pc = estrdat;
 }
 
+int
+dsname(Sym *s, int off, char *t, int n)
+{
+	Prog *p;
+
+	p = gins(ADATA, N, N);
+	p->from.type = D_EXTERN;
+	p->from.index = D_NONE;
+	p->from.offset = off;
+	p->from.scale = n;
+	p->from.sym = s;
+	
+	p->to.type = D_SCONST;
+	p->to.index = D_NONE;
+	memmove(p->to.sval, t, n);
+	return off + n;
+}
+
 /*
  * make a refer to the data s, s+len
  * emitting DATA if needed.
@@ -327,74 +345,13 @@ dumpdata(void)
 void
 datastring(char *s, int len, Addr *a)
 {
-	int w;
-	Prog *p;
-	Addr ac, ao;
-	static int gen;
-	struct {
-		Strlit lit;
-		char buf[100];
-	} tmp;
-
-	// string
-	memset(&ao, 0, sizeof(ao));
-	ao.type = D_STATIC;
-	ao.index = D_NONE;
-	ao.etype = TINT32;
-	ao.offset = 0;		// fill in
-
-	// constant
-	memset(&ac, 0, sizeof(ac));
-	ac.type = D_CONST;
-	ac.index = D_NONE;
-	ac.offset = 0;		// fill in
-
-	// huge strings are made static to avoid long names.
-	if(len > 100) {
-		snprint(namebuf, sizeof(namebuf), ".string.%d", gen++);
-		ao.sym = lookup(namebuf);
-		ao.type = D_STATIC;
-	} else {
-		if(len > 0 && s[len-1] == '\0')
-			len--;
-		tmp.lit.len = len;
-		memmove(tmp.lit.s, s, len);
-		tmp.lit.s[len] = '\0';
-		len++;
-		snprint(namebuf, sizeof(namebuf), "\"%Z\"", &tmp.lit);
-		ao.sym = pkglookup(namebuf, stringpkg);
-		ao.type = D_EXTERN;
-	}
-	*a = ao;
-
-	// only generate data the first time.
-	if(ao.sym->flags & SymUniq)
-		return;
-	ao.sym->flags |= SymUniq;
-
-	data();
-	for(w=0; w<len; w+=8) {
-		p = pc;
-		gins(ADATA, N, N);
-
-		// DATA s+w, [NSNAME], $"xxx"
-		p->from = ao;
-		p->from.offset = w;
-
-		p->from.scale = NSNAME;
-		if(w+8 > len)
-			p->from.scale = len-w;
-
-		p->to = ac;
-		p->to.type = D_SCONST;
-		p->to.offset = len;
-		memmove(p->to.sval, s+w, p->from.scale);
-	}
-	p = pc;
-	ggloblsym(ao.sym, len, ao.type == D_EXTERN);
-	if(ao.type == D_STATIC)
-		p->from.type = D_STATIC;
-	text();
+	Sym *sym;
+	
+	sym = stringsym(s, len);
+	a->type = D_EXTERN;
+	a->sym = sym;
+	a->offset = widthptr+4;  // skip header
+	a->etype = TINT32;
 }
 
 /*
@@ -404,76 +361,13 @@ datastring(char *s, int len, Addr *a)
 void
 datagostring(Strlit *sval, Addr *a)
 {
-	Prog *p;
-	Addr ac, ao, ap;
-	int32 wi, wp;
-	static int gen;
-
-	memset(&ac, 0, sizeof(ac));
-	memset(&ao, 0, sizeof(ao));
-	memset(&ap, 0, sizeof(ap));
-
-	// constant
-	ac.type = D_CONST;
-	ac.index = D_NONE;
-	ac.offset = 0;			// fill in
-
-	// string len+ptr
-	ao.type = D_STATIC;		// fill in
-	ao.index = D_NONE;
-	ao.etype = TINT32;
-	ao.sym = nil;			// fill in
-
-	// $string len+ptr
-	datastring(sval->s, sval->len, &ap);
-	ap.index = ap.type;
-	ap.type = D_ADDR;
-	ap.etype = TINT32;
-
-	wi = types[TUINT32]->width;
-	wp = types[tptr]->width;
-
-	if(ap.index == D_STATIC) {
-		// huge strings are made static to avoid long names
-		snprint(namebuf, sizeof(namebuf), ".gostring.%d", ++gen);
-		ao.sym = lookup(namebuf);
-		ao.type = D_STATIC;
-	} else {
-		// small strings get named by their contents,
-		// so that multiple modules using the same string
-		// can share it.
-		snprint(namebuf, sizeof(namebuf), "\"%Z\"", sval);
-		ao.sym = pkglookup(namebuf, gostringpkg);
-		ao.type = D_EXTERN;
-	}
-
-	*a = ao;
-	if(ao.sym->flags & SymUniq)
-		return;
-	ao.sym->flags |= SymUniq;
-
-	data();
-	// DATA gostring, wp, $cstring
-	p = pc;
-	gins(ADATA, N, N);
-	p->from = ao;
-	p->from.scale = wp;
-	p->to = ap;
-
-	// DATA gostring+wp, wi, $len
-	p = pc;
-	gins(ADATA, N, N);
-	p->from = ao;
-	p->from.offset = wp;
-	p->from.scale = wi;
-	p->to = ac;
-	p->to.offset = sval->len;
-
-	p = pc;
-	ggloblsym(ao.sym, types[TSTRING]->width, ao.type == D_EXTERN);
-	if(ao.type == D_STATIC)
-		p->from.type = D_STATIC;
-	text();
+	Sym *sym;
+	
+	sym = stringsym(sval->s, sval->len);
+	a->type = D_EXTERN;
+	a->sym = sym;
+	a->offset = 0;  // header
+	a->etype = TINT32;
 }
 
 void
diff --git a/src/cmd/8l/l.h b/src/cmd/8l/l.h
index 62f4702573..ac0f3953f0 100644
--- a/src/cmd/8l/l.h
+++ b/src/cmd/8l/l.h
@@ -139,6 +139,7 @@ struct	Sym
 	int32	plt;
 	int32	got;
 	Sym*	hash;	// in hash table
+	Sym*	allsym;	// in all symbol list
 	Sym*	next;	// in text or data list
 	Sym*	sub;	// in sub list
 	Sym*	outer;	// container of sub
@@ -169,7 +170,6 @@ struct	Optab
 
 enum
 {
-	NHASH		= 10007,
 	MINSIZ		= 4,
 	STRINGSZ	= 200,
 	MINLC		= 1,
diff --git a/src/cmd/gc/go.h b/src/cmd/gc/go.h
index 39c316f2e5..bb258a193d 100644
--- a/src/cmd/gc/go.h
+++ b/src/cmd/gc/go.h
@@ -1001,8 +1001,10 @@ int	duint32(Sym *s, int off, uint32 v);
 int	duint64(Sym *s, int off, uint64 v);
 int	duint8(Sym *s, int off, uint8 v);
 int	duintptr(Sym *s, int off, uint64 v);
+int	dsname(Sym *s, int off, char *dat, int ndat);
 void	dumpobj(void);
 void	ieeedtod(uint64 *ieee, double native);
+Sym*	stringsym(char*, int);
 
 /*
  *	print.c
@@ -1237,3 +1239,5 @@ void	patch(Prog*, Prog*);
 void	zfile(Biobuf *b, char *p, int n);
 void	zhist(Biobuf *b, int line, vlong offset);
 void	zname(Biobuf *b, Sym *s, int t);
+void	data(void);
+void	text(void);
diff --git a/src/cmd/gc/lex.c b/src/cmd/gc/lex.c
index b1e778d843..bfd96274ed 100644
--- a/src/cmd/gc/lex.c
+++ b/src/cmd/gc/lex.c
@@ -124,9 +124,6 @@ main(int argc, char *argv[])
 	runtimepkg = mkpkg(strlit("runtime"));
 	runtimepkg->name = "runtime";
 
-	stringpkg = mkpkg(strlit("string"));
-	stringpkg->name = "string";
-
 	typepkg = mkpkg(strlit("type"));
 	typepkg->name = "type";
 
diff --git a/src/cmd/gc/obj.c b/src/cmd/gc/obj.c
index fbabe0d43a..9f4b7b318d 100644
--- a/src/cmd/gc/obj.c
+++ b/src/cmd/gc/obj.c
@@ -235,3 +235,57 @@ duintptr(Sym *s, int off, uint64 v)
 {
 	return duintxx(s, off, v, widthptr);
 }
+
+Sym*
+stringsym(char *s, int len)
+{
+	static int gen;
+	Sym *sym;
+	int off, n, m;
+	struct {
+		Strlit lit;
+		char buf[110];
+	} tmp;
+	Pkg *pkg;
+
+	if(len > 100) {
+		// huge strings are made static to avoid long names
+		snprint(namebuf, sizeof(namebuf), ".gostring.%d", ++gen);
+		pkg = localpkg;
+	} else {
+		// small strings get named by their contents,
+		// so that multiple modules using the same string
+		// can share it.
+		tmp.lit.len = len;
+		memmove(tmp.lit.s, s, len);
+		tmp.lit.s[len] = '\0';
+		snprint(namebuf, sizeof(namebuf), "\"%Z\"", &tmp);
+		pkg = gostringpkg;
+	}
+	sym = pkglookup(namebuf, pkg);
+	
+	// SymUniq flag indicates that data is generated already
+	if(sym->flags & SymUniq)
+		return sym;
+	sym->flags |= SymUniq;
+	
+	data();
+	off = 0;
+	
+	// string header
+	off = dsymptr(sym, off, sym, widthptr+4);
+	off = duint32(sym, off, len);
+	
+	// string data
+	for(n=0; n<len; n+=m) {
+		m = 8;
+		if(m > len-n)
+			m = len-n;
+		off = dsname(sym, off, s+n, m);
+	}
+	off = duint8(sym, off, 0);  // terminating NUL for runtime
+	ggloblsym(sym, off, 1);
+	text();
+	
+	return sym;	
+}
diff --git a/src/cmd/gc/reflect.c b/src/cmd/gc/reflect.c
index 6b86462c44..b98e820c6d 100644
--- a/src/cmd/gc/reflect.c
+++ b/src/cmd/gc/reflect.c
@@ -348,17 +348,19 @@ dimportpath(Pkg *p)
  * uncommonType
  * ../../pkg/runtime/type.go:/uncommonType
  */
-static Sym*
-dextratype(Type *t)
+static int
+dextratype(Sym *sym, int off, Type *t, int ptroff)
 {
 	int ot, n;
-	char *p;
 	Sym *s;
 	Sig *a, *m;
 
 	m = methods(t);
 	if(t->sym == nil && m == nil)
-		return nil;
+		return off;
+	
+	// fill in *extraType pointer in header
+	dsymptr(sym, ptroff, sym, off);
 
 	n = 0;
 	for(a=m; a; a=a->link) {
@@ -366,9 +368,8 @@ dextratype(Type *t)
 		n++;
 	}
 
-	p = smprint("_.%#T", t);
-	s = pkglookup(p, typepkg);
-	ot = 0;
+	ot = off;
+	s = sym;
 	if(t->sym) {
 		ot = dgostringptr(s, ot, t->sym->name);
 		if(t != types[t->etype])
@@ -402,9 +403,8 @@ dextratype(Type *t)
 		else
 			ot = duintptr(s, ot, 0);
 	}
-	ggloblsym(s, ot, 0);
 
-	return s;
+	return ot;
 }
 
 enum {
@@ -570,7 +570,6 @@ static int
 dcommontype(Sym *s, int ot, Type *t)
 {
 	int i;
-	Sym *s1;
 	Sym *sptr;
 	char *p;
 
@@ -582,8 +581,6 @@ dcommontype(Sym *s, int ot, Type *t)
 	else
 		sptr = weaktypesym(ptrto(t));
 
-	s1 = dextratype(t);
-
 	// empty interface pointing at this type.
 	// all the references that we emit are *interface{};
 	// they point here.
@@ -620,11 +617,14 @@ dcommontype(Sym *s, int ot, Type *t)
 	longsymnames = 0;
 	ot = dgostringptr(s, ot, p);	// string
 	free(p);
-	if(s1)
-		ot = dsymptr(s, ot, s1, 0);	// extraType
-	else
-		ot = duintptr(s, ot, 0);
-	ot = dsymptr(s, ot, sptr, 0);  // ptr to type
+	
+	// skip pointer to extraType,
+	// which follows the rest of this type structure.
+	// caller will fill in if needed.
+	// otherwise linker will assume 0.
+	ot += widthptr;
+
+	ot = dsymptr(s, ot, sptr, 0);  // ptrto type
 	return ot;
 }
 
@@ -691,7 +691,7 @@ weaktypesym(Type *t)
 static Sym*
 dtypesym(Type *t)
 {
-	int ot, n, isddd, dupok;
+	int ot, xt, n, isddd, dupok;
 	Sym *s, *s1, *s2;
 	Sig *a, *m;
 	Type *t1, *tbase;
@@ -723,15 +723,18 @@ dtypesym(Type *t)
 
 ok:
 	ot = 0;
+	xt = 0;
 	switch(t->etype) {
 	default:
 		ot = dcommontype(s, ot, t);
+		xt = ot - 2*widthptr;
 		break;
 
 	case TARRAY:
 		// ../../pkg/runtime/type.go:/ArrayType
 		s1 = dtypesym(t->type);
 		ot = dcommontype(s, ot, t);
+		xt = ot - 2*widthptr;
 		ot = dsymptr(s, ot, s1, 0);
 		if(t->bound < 0)
 			ot = duintptr(s, ot, -1);
@@ -743,6 +746,7 @@ ok:
 		// ../../pkg/runtime/type.go:/ChanType
 		s1 = dtypesym(t->type);
 		ot = dcommontype(s, ot, t);
+		xt = ot - 2*widthptr;
 		ot = dsymptr(s, ot, s1, 0);
 		ot = duintptr(s, ot, t->chan);
 		break;
@@ -759,6 +763,7 @@ ok:
 			dtypesym(t1->type);
 
 		ot = dcommontype(s, ot, t);
+		xt = ot - 2*widthptr;
 		ot = duint8(s, ot, isddd);
 
 		// two slice headers: in and out.
@@ -790,6 +795,7 @@ ok:
 
 		// ../../pkg/runtime/type.go:/InterfaceType
 		ot = dcommontype(s, ot, t);
+		xt = ot - 2*widthptr;
 		ot = dsymptr(s, ot, s, ot+widthptr+2*4);
 		ot = duint32(s, ot, n);
 		ot = duint32(s, ot, n);
@@ -806,6 +812,7 @@ ok:
 		s1 = dtypesym(t->down);
 		s2 = dtypesym(t->type);
 		ot = dcommontype(s, ot, t);
+		xt = ot - 2*widthptr;
 		ot = dsymptr(s, ot, s1, 0);
 		ot = dsymptr(s, ot, s2, 0);
 		break;
@@ -820,6 +827,7 @@ ok:
 		// ../../pkg/runtime/type.go:/PtrType
 		s1 = dtypesym(t->type);
 		ot = dcommontype(s, ot, t);
+		xt = ot - 2*widthptr;
 		ot = dsymptr(s, ot, s1, 0);
 		break;
 
@@ -832,6 +840,7 @@ ok:
 			n++;
 		}
 		ot = dcommontype(s, ot, t);
+		xt = ot - 2*widthptr;
 		ot = dsymptr(s, ot, s, ot+widthptr+2*4);
 		ot = duint32(s, ot, n);
 		ot = duint32(s, ot, n);
@@ -853,7 +862,7 @@ ok:
 		}
 		break;
 	}
-
+	ot = dextratype(s, ot, t, xt);
 	ggloblsym(s, ot, dupok);
 	return s;
 }
diff --git a/src/cmd/ld/data.c b/src/cmd/ld/data.c
index 5d7394463d..32dba45964 100644
--- a/src/cmd/ld/data.c
+++ b/src/cmd/ld/data.c
@@ -733,18 +733,16 @@ dodata(void)
 	last = nil;
 	datap = nil;
 
-	for(h=0; h<NHASH; h++) {
-		for(s=hash[h]; s!=S; s=s->hash){
-			if(!s->reachable || s->special)
-				continue;
-			if(STEXT < s->type && s->type < SXREF) {
-				if(last == nil)
-					datap = s;
-				else
-					last->next = s;
-				s->next = nil;
-				last = s;
-			}
+	for(s=allsym; s!=S; s=s->allsym) {
+		if(!s->reachable || s->special)
+			continue;
+		if(STEXT < s->type && s->type < SXREF) {
+			if(last == nil)
+				datap = s;
+			else
+				last->next = s;
+			s->next = nil;
+			last = s;
 		}
 	}
 
diff --git a/src/cmd/ld/dwarf.c b/src/cmd/ld/dwarf.c
index ace38cbc53..bfdb1e7989 100644
--- a/src/cmd/ld/dwarf.c
+++ b/src/cmd/ld/dwarf.c
@@ -989,8 +989,8 @@ lookup_or_diag(char *n)
 {
 	Sym *s;
 
-	s = lookup(n, 0);
-	if (s->size == 0) {
+	s = rlookup(n, 0);
+	if (s == nil || s->size == 0) {
 		diag("dwarf: missing type: %s", n);
 		errorexit();
 	}
@@ -1462,10 +1462,6 @@ defdwsymb(Sym* sym, char *s, int t, vlong v, vlong size, int ver, Sym *gotype)
 
 	if (strncmp(s, "go.string.", 10) == 0)
 		return;
-	if (strncmp(s, "string.", 7) == 0)
-		return;
-	if (strncmp(s, "type._.", 7) == 0)
-		return;
 
 	if (strncmp(s, "type.", 5) == 0 && strcmp(s, "type.*") != 0) {
 		defgotype(sym);
@@ -2325,7 +2321,7 @@ dwarfemitdebugsections(void)
 {
 	vlong infoe;
 	DWDie* die;
-
+return;
 	// For diagnostic messages.
 	newattr(&dwtypes, DW_AT_name, DW_CLS_STRING, strlen("dwtypes"), "dwtypes");
 
diff --git a/src/cmd/ld/elf.c b/src/cmd/ld/elf.c
index d5b0b03111..b0cce4985d 100644
--- a/src/cmd/ld/elf.c
+++ b/src/cmd/ld/elf.c
@@ -336,7 +336,7 @@ void
 elfdynhash(void)
 {
 	Sym *s, *sy;
-	int i, h, nbucket, b;
+	int i, nbucket, b;
 	uchar *pc;
 	uint32 hc, g;
 	uint32 *chain, *buckets;
@@ -367,26 +367,24 @@ elfdynhash(void)
 	}
 	memset(chain, 0, nsym * sizeof(uint32));
 	memset(buckets, 0, nbucket * sizeof(uint32));
-	for(h = 0; h<NHASH; h++) {
-		for(sy=hash[h]; sy!=S; sy=sy->hash) {
-			if (sy->dynid <= 0)
-				continue;
-
-			hc = 0;
-			name = sy->dynimpname;
-			if(name == nil)
-				name = sy->name;
-			for(pc = (uchar*)name; *pc; pc++) {
-				hc = (hc<<4) + *pc;
-				g = hc & 0xf0000000;
-				hc ^= g >> 24;
-				hc &= ~g;
-			}
-
-			b = hc % nbucket;
-			chain[sy->dynid] = buckets[b];
-			buckets[b] = sy->dynid;
+	for(sy=allsym; sy!=S; sy=sy->allsym) {
+		if (sy->dynid <= 0)
+			continue;
+
+		hc = 0;
+		name = sy->dynimpname;
+		if(name == nil)
+			name = sy->name;
+		for(pc = (uchar*)name; *pc; pc++) {
+			hc = (hc<<4) + *pc;
+			g = hc & 0xf0000000;
+			hc ^= g >> 24;
+			hc &= ~g;
 		}
+
+		b = hc % nbucket;
+		chain[sy->dynid] = buckets[b];
+		buckets[b] = sy->dynid;
 	}
 
 	adduint32(s, nbucket);
diff --git a/src/cmd/ld/go.c b/src/cmd/ld/go.c
index b76e469aed..055163d089 100644
--- a/src/cmd/ld/go.c
+++ b/src/cmd/ld/go.c
@@ -658,8 +658,7 @@ deadcode(void)
 	else
 		last->next = nil;
 	
-	for(i=0; i<NHASH; i++)
-	for(s = hash[i]; s != S; s = s->hash)
+	for(s = allsym; s != S; s = s->allsym)
 		if(strncmp(s->name, "weak.", 5) == 0) {
 			s->special = 1;  // do not lay out in data segment
 			s->reachable = 1;
@@ -670,16 +669,14 @@ deadcode(void)
 void
 doweak(void)
 {
-	int i;
 	Sym *s, *t;
 
 	// resolve weak references only if
 	// target symbol will be in binary anyway.
-	for(i=0; i<NHASH; i++)
-	for(s = hash[i]; s != S; s = s->hash) {
+	for(s = allsym; s != S; s = s->allsym) {
 		if(strncmp(s->name, "weak.", 5) == 0) {
-			t = lookup(s->name+5, s->version);
-			if(t->type != 0 && t->reachable) {
+			t = rlookup(s->name+5, s->version);
+			if(t && t->type != 0 && t->reachable) {
 				s->value = t->value;
 				s->type = t->type;
 			} else {
diff --git a/src/cmd/ld/lib.c b/src/cmd/ld/lib.c
index e645502b33..75776bbc24 100644
--- a/src/cmd/ld/lib.c
+++ b/src/cmd/ld/lib.c
@@ -470,8 +470,8 @@ eof:
 	diag("truncated object file: %s", pn);
 }
 
-Sym*
-lookup(char *symb, int v)
+static Sym*
+_lookup(char *symb, int v, int creat)
 {
 	Sym *s;
 	char *p;
@@ -485,10 +485,12 @@ lookup(char *symb, int v)
 	// not if(h < 0) h = ~h, because gcc 4.3 -O2 miscompiles it.
 	h &= 0xffffff;
 	h %= NHASH;
+	c = symb[0];
 	for(s = hash[h]; s != S; s = s->hash)
-		if(s->version == v)
 		if(memcmp(s->name, symb, l) == 0)
 			return s;
+	if(!creat)
+		return nil;
 
 	s = mal(sizeof(*s));
 	if(debug['v'] > 1)
@@ -508,9 +510,25 @@ lookup(char *symb, int v)
 	s->size = 0;
 	hash[h] = s;
 	nsymbol++;
+	
+	s->allsym = allsym;
+	allsym = s;
 	return s;
 }
 
+Sym*
+lookup(char *name, int v)
+{
+	return _lookup(name, v, 1);
+}
+
+// read-only lookup
+Sym*
+rlookup(char *name, int v)
+{
+	return _lookup(name, v, 0);
+}
+
 void
 copyhistfrog(char *buf, int nbuf)
 {
@@ -1283,11 +1301,9 @@ headtype(char *name)
 void
 undef(void)
 {
-	int i;
 	Sym *s;
 
-	for(i=0; i<NHASH; i++)
-	for(s = hash[i]; s != S; s = s->hash)
+	for(s = allsym; s != S; s = s->allsym)
 		if(s->type == SXREF)
 			diag("%s(%d): not defined", s->name, s->version);
 }
diff --git a/src/cmd/ld/lib.h b/src/cmd/ld/lib.h
index fbd372b23d..df90923612 100644
--- a/src/cmd/ld/lib.h
+++ b/src/cmd/ld/lib.h
@@ -56,6 +56,8 @@ enum
 	SDYNIMPORT,
 
 	SSUB = 1<<8,	/* sub-symbol, linked from parent via ->sub list */
+	
+	NHASH = 100003,
 };
 
 typedef struct Library Library;
@@ -106,6 +108,7 @@ EXTERN	Library*	library;
 EXTERN	int	libraryp;
 EXTERN	int	nlibrary;
 EXTERN	Sym*	hash[NHASH];
+EXTERN	Sym*	allsym;
 EXTERN	Sym*	histfrog[MAXHIST];
 EXTERN	uchar	fnuxi8[8];
 EXTERN	uchar	fnuxi4[4];
@@ -133,6 +136,7 @@ void	asmlc(void);
 void	histtoauto(void);
 void	collapsefrog(Sym *s);
 Sym*	lookup(char *symb, int v);
+Sym*	rlookup(char *symb, int v);
 void	nuxiinit(void);
 int	find1(int32 l, int c);
 int	find2(int32 l, int c);
diff --git a/src/cmd/ld/pe.c b/src/cmd/ld/pe.c
index e72b0b2a0d..0d4240e36d 100644
--- a/src/cmd/ld/pe.c
+++ b/src/cmd/ld/pe.c
@@ -171,12 +171,10 @@ initdynimport(void)
 	Imp *m;
 	Dll *d;
 	Sym *s, *dynamic;
-	int i;
 
 	dr = nil;
 	
-	for(i=0; i<NHASH; i++)
-	for(s = hash[i]; s != S; s = s->hash) {
+	for(s = allsym; s != S; s = s->allsym) {
 		if(!s->reachable || !s->dynimpname || s->dynexport)
 			continue;
 		for(d = dr; d != nil; d = d->next) {
@@ -312,12 +310,10 @@ scmp(const void *p1, const void *p2)
 static void
 initdynexport(void)
 {
-	int i;
 	Sym *s;
 	
 	nexport = 0;
-	for(i=0; i<NHASH; i++)
-	for(s = hash[i]; s != S; s = s->hash) {
+	for(s = allsym; s != S; s = s->allsym) {
 		if(!s->reachable || !s->dynimpname || !s->dynexport)
 			continue;
 		if(nexport+1 > sizeof(dexport)/sizeof(dexport[0])) {
diff --git a/src/cmd/ld/symtab.c b/src/cmd/ld/symtab.c
index f1d44058e0..aefe0b1af0 100644
--- a/src/cmd/ld/symtab.c
+++ b/src/cmd/ld/symtab.c
@@ -340,7 +340,6 @@ putsymb(Sym *s, char *name, int t, vlong v, vlong size, int ver, Sym *typ)
 void
 symtab(void)
 {
-	int32 h;
 	Sym *s;
 
 	// Define these so that they'll get put into the symbol table.
@@ -361,11 +360,6 @@ symtab(void)
 	s->size = 0;
 	s->reachable = 1;
 
-	s = lookup("string.*", 0);
-	s->type = SSTRING;
-	s->size = 0;
-	s->reachable = 1;
-
 	s = lookup("go.string.*", 0);
 	s->type = SGOSTRING;
 	s->size = 0;
@@ -380,22 +374,16 @@ symtab(void)
 	// within a type they sort by size, so the .* symbols
 	// just defined above will be first.
 	// hide the specific symbols.
-	for(h=0; h<NHASH; h++) {
-		for(s=hash[h]; s!=S; s=s->hash){
-			if(!s->reachable || s->special || s->type != SRODATA)
-				continue;
-			if(strncmp(s->name, "type.", 5) == 0) {
-				s->type = STYPE;
-				s->hide = 1;
-			}
-			if(strncmp(s->name, "string.", 7) == 0) {
-				s->type = SSTRING;
-				s->hide = 1;
-			}
-			if(strncmp(s->name, "go.string.", 10) == 0) {
-				s->type = SGOSTRING;
-				s->hide = 1;
-			}
+	for(s = allsym; s != S; s = s->allsym) {
+		if(!s->reachable || s->special || s->type != SRODATA)
+			continue;
+		if(strncmp(s->name, "type.", 5) == 0) {
+			s->type = STYPE;
+			s->hide = 1;
+		}
+		if(strncmp(s->name, "go.string.", 10) == 0) {
+			s->type = SGOSTRING;
+			s->hide = 1;
 		}
 	}