Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Dialogs parsing performance #28

Closed
Try opened this issue Nov 3, 2022 · 5 comments
Closed

Dialogs parsing performance #28

Try opened this issue Nov 3, 2022 · 5 comments
Assignees
Milestone

Comments

@Try
Copy link
Contributor

Try commented Nov 3, 2022

GameScript::loadDialogOU() become noticeably slower with phenix backend.

I haven't done proper profiling, but issue seem to be rooted in large amount of small allocations, while population hash-map.
Lazy profiling(debug break a few times) shows, that this place can be an issue:

	bool archive_reader_binsafe::read_object_begin(archive_object& obj) {
		...
		std::stringstream ss {line.substr(1, line.size() - 2)}; // substr creates a copy; and well stringstream known to be slow
		ss >> obj.object_name >> obj.class_name >> obj.version >> obj.index;
		return true;
	}
@Try Try changed the title Dialigs parsing performance Dialogs parsing performance Nov 3, 2022
@lmichaelis
Copy link
Member

Hm, that would mean that you should have observed slower load times everywhere, especially when loading the VOb tree. There might be optimisations that can be done in messages though.

@Try
Copy link
Contributor Author

Try commented Nov 5, 2022

I've made a few experiment locally:

  1. removing std::stringstream - generally nice, but not critical improvement.

  2. replacing messages::_m_blocks_by_name to sort + binary search - work quite well

// messages messages::parse(buffer& buf)
...
   std::sort(msgs.blocks.begin(), msgs.blocks.end(), [](const message_block& l, const message_block& r){
      return l.name<r.name;
      });
   return msgs;
   }

const message_block* messages::block_by_name(std::string_view name) const {
    auto it = std::lower_bound(blocks.begin(), blocks.end(), name, [](const message_block& l, std::string_view name) {
      return l.name < name;
      });
    if (it!=blocks.end())
      return &*it;
    return nullptr;
    }

@lmichaelis
Copy link
Member

It certainly makes sense that not allocating potentially thousands of small std::strings would make loading faster. Are you sure that in-game performance is actually acceptable using binary search instead of std::unordered_map's O(1) access times?

@Try
Copy link
Contributor Author

Try commented Nov 5, 2022

Yes, I've tested this solution locally.
Also fetching block_by_name relatively rare case (roughly a 1 call per 3 seconds). Worst what can happen is spike at search call.

@lmichaelis lmichaelis self-assigned this Nov 6, 2022
@lmichaelis lmichaelis added this to the v1.1.0 milestone Nov 6, 2022
lmichaelis added a commit that referenced this issue Nov 6, 2022
The allocation of many thousands of small strings as keys of the
`std::unordered_map` used for looking up blocks by their name is not
very fast.

Using binary search instead improves parsing performance and decreases
memory usage while still keeping block lookup performance within an
acceptable range.
@lmichaelis
Copy link
Member

Implemented :)

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

No branches or pull requests

2 participants