Skip to content

Improve performance of search iterators #390

@deniskoronchik

Description

@deniskoronchik

ScTemplateNamedStruct builds every time from scratch for each iteration. This code is in

void MakeResult()
{
    ScTemplateNamedStruct::Builder builder(m_result);
    for (auto const & r : m_repls)
    {
      SC_ASSERT(r.second.addr.IsValid(), ());
      builder.Add(r.first, r.second.addr);
    }

    // iterate all addrs and append missed into result
    for (ScAddr const & addr : m_resultAddrs)
      builder.Add(addr);
}

Main problem there that builder create hash table of replacements and elements vector from scratch. But there are no any reason to do that, because each result have the same structure.

We can cache result structure and just place founded elements into m_elements of ScTemplateNamedStruct at the same places. This can be achieved by adding resultIndex field into ScTemplateArg. This can be done during template build. Then result building became very simple:

  • Allocate vector for all elements
  • Setup replacement names table one time
  • Fill result elements on each iteration by using resultIndex as index

Also it is possible to improve performance of replacements in different algorithms that work with templates. It would be faster to work with number than with string.

Metadata

Metadata

Labels

Type

No type

Projects

No projects

Relationships

None yet

Development

No branches or pull requests

Issue actions