indexOf/lastIndexOf vs StringSearchCache

Benchmark created on August 2, 2024

Setup

var target_string_left = 10000;


var createStringSearchCache = (function() {
	//- uses a moving window around the last referenced index
	//- returns cached found indices for any value searched for
	//- when searching from index beyond cache, moves window and finds new values.
	function createStringSearchCache(string) {
		var data = { string: string, cache: {} };
		return new Proxy(data, proxy_handler);
	}

	var DATA = Symbol("string_search_cache_data");
	
	//! holds relevant cache from current proxy running
	//  never recursive, so should be okay
	var c, search_from;
	var UNSET = -2, UNFOUND = -1;
	var proxy_handler = {
		get(target, prop, receiver) {
			if (prop === "string") { return target.string; }
			else if (prop === DATA) { return target; }
			else if (prop in this.proto) { return this.proto[prop]; }
			else { throw new Error(`Cannot access property ${JSON.stringify(prop)}.`); }
		},
		set(target, prop, value, receiver) {
			//* allow adding to start/end of string?
			throw new Error(`Cannot set properties on StringSearchCache.`);
		},

		proto: {
			findClosest: function findClosest(index, direction, find) {
				//* if -1 found, find earliest 
				//  to avoid ever making that (more expensive) check again?
				
				if (typeof direction !== "number" || isNaN(direction)) {
					throw new Error(`Invalid direction ${JSON.stringify(direction)}.`);
				}
				else if (find === "") {
					if (index < 0) { return 0; }
					else if (index >= this.string.length) { return string.length; }
					else { return index; }
				}
				else {
					c = ensure_cache(this[DATA], find);
					if (c.none) { return -1; }

					if (direction === 0) {
						if (this.string[index] === find) {
							c.previous = index; c.next = index;
							return index;
						}
						else {
							return -1;
						}
					}
						
					// can only be -1 (unfound) or 0+ (found)
					
					// creating ranges checks are unecessary
					//   searching prev, prev -> prev_from, send prev
					//   searching next, next_from -> next, send next

					// when to find these?
					// first time check unfound to avoid ever making that check again?
					//   searching prev, index < first, send -1
					//   searching next, index > last, send -1

					// within other range, search from closest of that range.
					
					// otherwise, search.
					//   searching prev, next_from < index < found next, search from next_from
					//   - else, search from index
					//   searching next, found prev < index < prev_from, search from prev_from
					//   - else, search from index

					// >= (can find same index)
					else if (direction > 0) {
						if (index === c.last) { return index; }
						else if (index > c.last) { return -1; }
						else if ((index === c.next) || (index >= c.next_from && index < c.next)) {
							return c.next;
						}
						else {
							c.next_from = index;
							if (c.prev !== -1 && index >= c.prev && index <= c.prev_from) {
								return (c.next = this.string.indexOf(find, c.prev_from));
							}
							else {
								return (c.next = this.string.indexOf(find, index));
							}
						}
					}
					// < (cannot find same index)
					else if (direction < 0) {
						if (index === c.first) { return index; }
						else if (index < c.first) { return -1; }
						else if ((index === c.prev) || (index >= c.prev && index <= c.prev_from)) {
							return c.prev;
						}
						else {
							c.prev_from = index;
							if (c.next !== -1 && index >= c.next_from && index <= c.next) {
								return (c.prev = this.string.lastIndexOf(find, c.next_from));
							}
							else {
								return (c.prev = this.string.lastIndexOf(find, index));
							}
						}
					}
					else {
						// FAILSAFE should not happen
						throw new Error(`Direction ${JSON.stringify(direction)} not matched.`);
					}
				}
			},
			hasClosest: function hasClosest(index, direction, find) {
				return this.findClosest(...arguments) !== -1;
			}
		}
	};

	// -2: unset
	// -1: none found
	// 0+: index of find
	var none, first, last;
	function ensure_cache(data, substr) {
		if (substr in data.cache) { return data.cache[substr]; }
		else {
			none = false; last = -1;
			
			first = data.string.indexOf(substr);
			if (first === -1) { none = true; }
			else { last = data.string.lastIndexOf(substr); }
			
			return (data.cache[substr] = {
				none:none,
				first:first, prev:-1, prev_from:0,
				next_from:data.string.length, next:-1, last:last
			});
		}
	}
	
	return createStringSearchCache;
})();

var per_random = 18;
var randoms = Math.ceil((target_string_left-2)/per_random);
var string = "x" + Array(randoms).fill(1).map(function() {
	var r = Math.random();
	return r < 0.001 ? "I" : r.toString().substr(2); }).join("") + "x";
console.log(string);
var string_search_cache = createStringSearchCache(string);

Test runner

for (var i = 0; i < string.length; i++) {
	string.indexOf("0", i);
	string.lastIndexOf("0", i);

	string.indexOf("I", i);
	string.lastIndexOf("I", i);
	
	string.indexOf("x", i);
	string.lastIndexOf("x", i);
	
	string.indexOf("?", i);
	string.lastIndexOf("?", i);
}

for (var i = 0; i < string.length; i++) {
	string_search_cache.findClosest("0", 1, i);
	string_search_cache.findClosest("0", -1, i);

	string_search_cache.findClosest("I", 1, i);
	string_search_cache.findClosest("I", -1, i);
	
	string_search_cache.findClosest("x", 1, i);
	string_search_cache.findClosest("x", -1, i);

	string_search_cache.findClosest("?", 1, i);
	string_search_cache.findClosest("?", -1, i);
}

Revisions

You can edit these tests or add more tests to this page by appending /edit to the URL.

• Revision 1: published on August 2, 2024