Sort the `ENTITIES` array to allow for binary searching

[SabrinaJewson]

Although a binary search is slower than a hashmap lookup (on my machine, the former is 83ns, a std hashmap lookup is 16ns, while a rustc_hash hashmap lookup is 5ns), constructing a hashmap still takes a while (38μs on my machine), meaning one has to perform ~500 lookups before it becomes profitable performance-wise to use a hashmap. Since I expect most use-cases will not be parsing hundreds of entities like that (and parsing entities is not the performance bottleneck most of the time anyway), I think that allowing for direct binary search would be good.

[SabrinaJewson]

Of course, this does raise the question of why this crate doesn’t provide a map, since that would result in even faster lookup. I guess the main reason to avoid maps is the space overhead, but this would be solved with a perfect hash function. The phf crate performs less well then a rustc_hash hashmap (since it uses SipHash); alternatively, it may not be hard to just manually find a fast perfect hash function, in which case we could very simply expose a function:

pub fn index(s: &str) -> usize;

There would be no penalty for the user with this approach.

[p-jackson]

There isn't a 1-to-1 mapping of entities to "characters" which is why this crate provides a flat array rather than a map. There are higher-level crates which can have a more opinionated API e.g. escapist, but this crate aims to just provide the static lifetime raw data.

The problem with taking a stance on mapping is that different package have different ways they will want to use the data: some will transform from entity to character, others from character to entity, so which would act as the map's key. Similarly with sorting ENTITIES: is it better to sort by code point or by entity?

At the moment the order of the entities is the same as what's pulled from w3.org. And I can see an argument for keeping it the same as them. But when I quickly scan the list it already looks sorted by entity. Is that not true?

The idea of exposing a perfect hash function is interesting though 🤔 Just for the case where someone just happens to be mapping from the entity to the character. I'll have a think about that.

[SabrinaJewson]

I suppose my main concern is that this crate is useless to me personally, because I want a PHF and so the runtime-only access isn’t needed. But really, for people who want a PHF I’m not sure it could be useful anyway.