From 173d1fd1c3fef385f73accc4b2bbb1b6f92ac3f5 Mon Sep 17 00:00:00 2001
From: Paul Guyot <pguyot@kallisys.net>
Date: Sun, 4 Jul 2010 15:08:47 +0200
Subject: beam_asm: Simplify string table generation for beams

The code for generating the string table (which is now
only used for bit syntax matching) in a BEAM file is quite
complicated and potentially expensive when compiling modules
with many thousands of clauses doing bit syntax matching.

Simplify and optimize the code using bit syntax and
binary:match/2 instead of the list operations in the
original code.
---
 lib/compiler/src/beam_dict.erl                     | 30 ++++++++++------------
 lib/compiler/test/compilation_SUITE.erl            | 13 +++++++++-
 .../test/compilation_SUITE_data/string_table.erl   |  8 ++++++
 3 files changed, 34 insertions(+), 17 deletions(-)
 create mode 100644 lib/compiler/test/compilation_SUITE_data/string_table.erl

(limited to 'lib')

diff --git a/lib/compiler/src/beam_dict.erl b/lib/compiler/src/beam_dict.erl
index 9164259a94..a1f994dfbd 100644
--- a/lib/compiler/src/beam_dict.erl
+++ b/lib/compiler/src/beam_dict.erl
@@ -33,7 +33,7 @@
 	 exports = []		    :: [{label(), arity(), label()}],
 	 locals = []		    :: [{label(), arity(), label()}],
 	 imports = gb_trees:empty() :: gb_tree(),      	%{{M,F,A},Index}
-	 strings = []		    :: string(),	%String pool
+	 strings = <<>>		    :: binary(),	%String pool
 	 lambdas = [],				%[{...}]
 	 literals = dict:new()	    :: dict(),	%Format: {Literal,Number}
 	 next_atom = 1		    :: pos_integer(),
@@ -119,10 +119,11 @@ import(Mod0, Name0, Arity, #asm{imports=Imp0,next_import=NextIndex}=D0)
 
 string(Str, Dict) when is_list(Str) ->
     #asm{strings=Strings,string_offset=NextOffset} = Dict,
-    case old_string(Str, Strings) of
+    StrBin = list_to_binary(Str),
+    case old_string(StrBin, Strings) of
 	none ->
-	    NewDict = Dict#asm{strings=Strings++Str,
-			       string_offset=NextOffset+length(Str)},
+	    NewDict = Dict#asm{strings = <<Strings/binary,StrBin/binary>>,
+			       string_offset=NextOffset+byte_size(StrBin)},
 	    {NextOffset,NewDict};
 	Offset when is_integer(Offset) ->
 	    {NextOffset-Offset,Dict}
@@ -187,7 +188,7 @@ import_table(#asm{imports=Imp,next_import=NumImports}) ->
     ImpTab = [MFA || {MFA,_} <- Sorted],
     {NumImports,ImpTab}.
 
--spec string_table(bdict()) -> {non_neg_integer(), [string()]}.
+-spec string_table(bdict()) -> {non_neg_integer(), binary()}.
 
 string_table(#asm{strings=Strings,string_offset=Size}) ->
     {Size,Strings}.
@@ -217,15 +218,12 @@ literal_table(#asm{literals=Tab,next_literal=NumLiterals}) ->
 my_term_to_binary(Term) ->
     term_to_binary(Term, [{minor_version,1}]).
 
-%% Search for string Str in the string pool Pool.
+%% Search for binary string Str in the binary string pool Pool.
 %%    old_string(Str, Pool) -> none | Index
--spec old_string(string(), string()) -> 'none' | pos_integer().
-
-old_string([C|Str]=Str0, [C|Pool]) ->
-    case lists:prefix(Str, Pool) of
-	true -> length(Pool)+1;
-	false -> old_string(Str0, Pool)
-    end;
-old_string([_|_]=Str, [_|Pool]) ->
-    old_string(Str, Pool);
-old_string([_|_], []) -> none.
+-spec old_string(binary(), binary()) -> 'none' | pos_integer().
+
+old_string(Str, Pool) ->
+    case binary:match(Pool, Str) of
+        nomatch -> none;
+        {Start,_Length} -> byte_size(Pool) - Start
+    end.
diff --git a/lib/compiler/test/compilation_SUITE.erl b/lib/compiler/test/compilation_SUITE.erl
index d4843c9eba..9c06740816 100644
--- a/lib/compiler/test/compilation_SUITE.erl
+++ b/lib/compiler/test/compilation_SUITE.erl
@@ -46,7 +46,7 @@ all(suite) ->
      trycatch_4, opt_crash,
      otp_5404,otp_5436,otp_5481,otp_5553,otp_5632,
      otp_5714,otp_5872,otp_6121,otp_6121a,otp_6121b,
-     otp_7202,otp_7345,on_load
+     otp_7202,otp_7345,on_load,string_table
     ].
 
 -define(comp(N),
@@ -596,4 +596,15 @@ otp_7345(ObjRef, _RdEnv, Args) ->
 		       10},
     id(LlUnitdataReq).
 
+%% Check the generation of the string table.
+
+string_table(Config) when is_list(Config) ->
+    ?line DataDir = ?config(data_dir, Config),
+    ?line File = filename:join(DataDir, "string_table.erl"),
+    ?line {ok,string_table,Beam,[]} = compile:file(File, [return, binary]),
+    ?line {ok,{string_table,[StringTableChunk]}} = beam_lib:chunks(Beam, ["StrT"]),
+    ?line {"StrT", <<"stringabletringtable">>} = StringTableChunk,
+    ok.
+
+
 id(I) -> I.
diff --git a/lib/compiler/test/compilation_SUITE_data/string_table.erl b/lib/compiler/test/compilation_SUITE_data/string_table.erl
new file mode 100644
index 0000000000..1da1d015dd
--- /dev/null
+++ b/lib/compiler/test/compilation_SUITE_data/string_table.erl
@@ -0,0 +1,8 @@
+-module(string_table).
+-export([f/1, g/1]).
+
+f(<<"string">>) -> string;
+f(<<"stringtable">>) -> stringtable.
+
+g(<<"stringtable">>) -> stringtable;
+g(<<"table">>) -> table.
-- 
cgit v1.2.3