thodg/libgit2/src/config_entries.c

• Show log

  Commit

• Hash : f2400a9c
  Author :
  Date : 2020-07-13T20:56:08
  

  config_entries: Avoid excessive map operations When appending config entries, we currently always first get the currently existing map entry and then afterwards update the map to contain the current config value. In the common scenario where keys aren't being overridden, this is the best we can do. But in case a key gets set multiple times, then we'll also perform these two map operations. In extreme cases, hashing the map keys will thus start to dominate performance. Let's optimize the pattern by using a separately allocated map entry. Currently, we always put the current list entry into the map and update it to get any overridden multivar. As these list entries are also used to iterate config entries, we cannot update them in-place in the map and are thus forced to always set the map to contain the new entry. But with a separately allocated map entry, we can now create one once per config key and insert it into the map. Whenever appending a new config value with the same key, we can now just update the map entry in-place instead of having to replace the map entry completely. This reduces calls to the hashing function by half and trades the improved runtime for one more allocation per unique config key. Given that the refactoring arguably improves code readability by splitting concerns of the `config_entry_list` type and not having to track it in two different structures, this alone would already be reason enough to take the trade. Given a pathological case of a gitconfig with 100.000 repeated keys and a section of length 10.000 characters, this reduces runtime by half from approximately 14 seconds to 7 seconds as expected.

Download

• src/config_entries.c

• /*
   * Copyright (C) the libgit2 contributors. All rights reserved.
   *
   * This file is part of libgit2, distributed under the GNU GPL v2 with
   * a Linking Exception. For full terms see the included COPYING file.
   */
  
  #include "config_entries.h"
  
  typedef struct config_entry_list {
  	struct config_entry_list *next;
  	struct config_entry_list *last;
  	git_config_entry *entry;
  } config_entry_list;
  
  typedef struct {
  	git_config_entry *entry;
  	bool multivar;
  } config_entry_map_head;
  
  typedef struct config_entries_iterator {
  	git_config_iterator parent;
  	git_config_entries *entries;
  	config_entry_list *head;
  } config_entries_iterator;
  
  struct git_config_entries {
  	git_refcount rc;
  	git_strmap *map;
  	config_entry_list *list;
  };
  
  int git_config_entries_new(git_config_entries **out)
  {
  	git_config_entries *entries;
  	int error;
  
  	entries = git__calloc(1, sizeof(git_config_entries));
  	GIT_ERROR_CHECK_ALLOC(entries);
  	GIT_REFCOUNT_INC(entries);
  
  	if ((error = git_strmap_new(&entries->map)) < 0)
  		git__free(entries);
  	else
  		*out = entries;
  
  	return error;
  }
  
  int git_config_entries_dup_entry(git_config_entries *entries, const git_config_entry *entry)
  {
  	git_config_entry *duplicated;
  	int error;
  
  	duplicated = git__calloc(1, sizeof(git_config_entry));
  	GIT_ERROR_CHECK_ALLOC(duplicated);
  
  	duplicated->name = git__strdup(entry->name);
  	GIT_ERROR_CHECK_ALLOC(duplicated->name);
  
  	if (entry->value) {
  		duplicated->value = git__strdup(entry->value);
  		GIT_ERROR_CHECK_ALLOC(duplicated->value);
  	}
  	duplicated->level = entry->level;
  	duplicated->include_depth = entry->include_depth;
  
  	if ((error = git_config_entries_append(entries, duplicated)) < 0)
  		goto out;
  
  out:
  	if (error && duplicated) {
  		git__free((char *) duplicated->name);
  		git__free((char *) duplicated->value);
  		git__free(duplicated);
  	}
  	return error;
  }
  
  int git_config_entries_dup(git_config_entries **out, git_config_entries *entries)
  {
  	git_config_entries *result = NULL;
  	config_entry_list *head;
  	int error;
  
  	if ((error = git_config_entries_new(&result)) < 0)
  		goto out;
  
  	for (head = entries->list; head; head = head->next)
  		if ((git_config_entries_dup_entry(result, head->entry)) < 0)
  			goto out;
  
  	*out = result;
  	result = NULL;
  
  out:
  	git_config_entries_free(result);
  	return error;
  }
  
  void git_config_entries_incref(git_config_entries *entries)
  {
  	GIT_REFCOUNT_INC(entries);
  }
  
  static void config_entries_free(git_config_entries *entries)
  {
  	config_entry_list *list = NULL, *next;
  	config_entry_map_head *head;
  
  	git_strmap_foreach_value(entries->map, head,
  		git__free((char *) head->entry->name); git__free(head)
  	);
  	git_strmap_free(entries->map);
  
  	list = entries->list;
  	while (list != NULL) {
  		next = list->next;
  		git__free((char *) list->entry->value);
  		git__free(list->entry);
  		git__free(list);
  		list = next;
  	}
  
  	git__free(entries);
  }
  
  void git_config_entries_free(git_config_entries *entries)
  {
  	if (entries)
  		GIT_REFCOUNT_DEC(entries, config_entries_free);
  }
  
  int git_config_entries_append(git_config_entries *entries, git_config_entry *entry)
  {
  	config_entry_list *list_head;
  	config_entry_map_head *map_head;
  
  	if ((map_head = git_strmap_get(entries->map, entry->name)) != NULL) {
  		map_head->multivar = true;
  		/*
  		 * This is a micro-optimization for configuration files
  		 * with a lot of same keys. As for multivars the entry's
  		 * key will be the same for all entries, we can just free
  		 * all except the first entry's name and just re-use it.
  		 */
  		git__free((char *) entry->name);
  		entry->name = map_head->entry->name;
  	} else {
  		map_head = git__calloc(1, sizeof(*map_head));
  		if ((git_strmap_set(entries->map, entry->name, map_head)) < 0)
  			return -1;
  	}
  	map_head->entry = entry;
  
  	list_head = git__calloc(1, sizeof(config_entry_list));
  	GIT_ERROR_CHECK_ALLOC(list_head);
  	list_head->entry = entry;
  
  	if (entries->list)
  		entries->list->last->next = list_head;
  	else
  		entries->list = list_head;
  	entries->list->last = list_head;
  
  	return 0;
  }
  
  int git_config_entries_get(git_config_entry **out, git_config_entries *entries, const char *key)
  {
  	config_entry_map_head *entry;
  	if ((entry = git_strmap_get(entries->map, key)) == NULL)
  		return GIT_ENOTFOUND;
  	*out = entry->entry;
  	return 0;
  }
  
  int git_config_entries_get_unique(git_config_entry **out, git_config_entries *entries, const char *key)
  {
  	config_entry_map_head *entry;
  
  	if ((entry = git_strmap_get(entries->map, key)) == NULL)
  		return GIT_ENOTFOUND;
  
  	if (entry->multivar) {
  		git_error_set(GIT_ERROR_CONFIG, "entry is not unique due to being a multivar");
  		return -1;
  	}
  
  	if (entry->entry->include_depth) {
  		git_error_set(GIT_ERROR_CONFIG, "entry is not unique due to being included");
  		return -1;
  	}
  
  	*out = entry->entry;
  
  	return 0;
  }
  
  static void config_iterator_free(git_config_iterator *iter)
  {
  	config_entries_iterator *it = (config_entries_iterator *) iter;
  	git_config_entries_free(it->entries);
  	git__free(it);
  }
  
  static int config_iterator_next(
  	git_config_entry **entry,
  	git_config_iterator *iter)
  {
  	config_entries_iterator *it = (config_entries_iterator *) iter;
  
  	if (!it->head)
  		return GIT_ITEROVER;
  
  	*entry = it->head->entry;
  	it->head = it->head->next;
  
  	return 0;
  }
  
  int git_config_entries_iterator_new(git_config_iterator **out, git_config_entries *entries)
  {
  	config_entries_iterator *it;
  
  	it = git__calloc(1, sizeof(config_entries_iterator));
  	GIT_ERROR_CHECK_ALLOC(it);
  	it->parent.next = config_iterator_next;
  	it->parent.free = config_iterator_free;
  	it->head = entries->list;
  	it->entries = entries;
  
  	git_config_entries_incref(entries);
  	*out = &it->parent;
  
  	return 0;
  }
  

Download