Re: table.concat - why so complex?

[Peter Cawley <lua@...>]

On Tue, Apr 6, 2010 at 1:52 PM, Gavin Wraith <gavin@wra1th.plus.com> wrote:
> In message <5EC08AEC9A25D746ABB7341DCE1E7A6090B2A2@mx.ellipsbv.local> you wrote:
>
>> My naive solution would be simple: Iterate over the array, add the
>> string
>> length of its members, add the required storage for any supplied
>> separator,
>> allocate the target string to the right, and memcpy() the array members
>> (and
>> any separators) over to their final location.
>
> You are presuming that Lua strings are stored in arrays, as a consecutive
> sequence of bytes, as in C. They are not.

Well colour me confused, as I was fairly certain that they were. At
the API level, lua_pushlstring receives an array of bytes and
lua_tolstring returns a (null terminated) array of bytes. I'm fairly
certain that internally, strings are stored as a TString structure
immediately followed in memory by a (null terminated) immutable array
of bytes. There is the string hash table which allows for quick lookup
of strings as to avoid creating the same string twice, but from the
looks of it, the actual TString structures do not move, and so the
"location" of a Lua string seems to be fairly well defined.

It has been previously noted that luaL_addlstring is fairly
inefficient, as it adds a single character at a time to the buffer,
rather than adding the whole string. As table.concat limits itself to
only working with strings, and hence sidesteps __concat, the method
used does indeed seem a little odd. It would be worth profiling an
implementation which builds up the result in a single buffer, along
the lines of the one below:
  size_t lsep, lresult, ls;
  int i, last;
  const char *res, *resptr, *s;
  const char *sep = luaL_optlstring(L, 2, "", &lsep);
  luaL_checktype(L, 1, LUA_TTABLE);
  i = luaL_optint(L, 3, 1);
  last = luaL_opt(L, luaL_checkint, 4, luaL_getn(L, 1));
  lresult = (last > i) ? (last - i) * lsep : 0;
  for (; i <= last; i++) {
    lua_rawgeti(L, 1, i);
    if (!lua_isstring(L, -1)) {
      luaL_error(L, "invalid value (%s) at index %d in table for "
                    LUA_QL("concat"), luaL_typename(L, -1), i);
    }
    lresult += lua_objlen(L, -1);
    lua_pop(L, 1);
  }
  res = resptr = lua_newuserdata(L, lresult);
  for (; i < last; i++) {
    lua_rawgeti(L, 1, i);
    s = lua_tolstring(L, -1, &ls);
    memcpy(resptr, s, ls);
    resptr += ls;
    memcpy(resptr, sep, lsep);
    resptr += lsep;
    lua_pop(L, 1);
  }
  if (i == last) {
    lua_rawgeti(L, 1, i);
    s = lua_tolstring(L, -1, &ls);
    memcpy(resptr, s, ls);
  }
  lua_pushlstring(L, res, lresult);
  return 1;