14.08.2025 01:12, Jeff Davis wrote:
On Mon, 2025-08-11 at 17:21 +0300, Alexander Borisov wrote:
[..]
Comments on the patch itself: The 0001 patch generalizes the two-step lookup process: first navigate branches to find the index into a partially-compacted sparse array, and then use that to get the index into the dense array. The branching code, the sparse array, and the dense array are all generated code. The reason for the two-step lookup is to keep the sparse array element size small (uint16), so that missing elements consume less space (missing elements still remain for small gaps). The full entry is kept in the dense array.
Yes, that's exactly right.
GenerateSparseArray.pm would be more descriptive than "Ranges.pm" for the new module. And we should probably include "sparse" in the name of the sparse arrays.
I don't mind, that's good.
The new module is responsible for generating the branching code as well as the sparse array; while the caller is reponsible for the dense arrays. For case mapping, one sparse array is used for four parallel arrays for the different case kinds (lower/title/upper/fold).
Yes, that's right.
The use of zero values for different purposes is getting confusing. It means "doesn't exist", but we are also reserving the zeroth element in the arrays. Would it be easier to just "#define EMPTY 0xFFFF" and then have the caller check for it? That way we don't need to reserve the zeroth array element, which should make it easier to avoid off-by-one errors.
Initially, that was the case; However, I subsequently concluded that creating magical values to define an element that was not found was not an ideal solution. I felt that 0 was easier to understand. I'm not entirely sure now, but maybe this will even help get rid of the comparison to 0. That is, we can get an element from the main table by index 0. It will be zeroed, and the algorithm will work as it should. However, it is not certain that this will have any effect on performance. In general, I don't have a firm position on this issue.
I think we can simplify the interface, as well. Why does the caller need to separately generate the ranges, then generate the table, then generate the branches? It's really all the same action and can be based on an input hash with a certain structure, and then return both the table and the branches, right?
Yes, it can be done in one go. But the separation was done intentionally. It makes the code more understandable, and, more importantly, it makes it easier for developers "from the street" to understand it and, if necessary, correct or supplement the algorithm. These are utilities, code for generating an algorithm that, let's say, will not be used very often, and I would not "compress" it. Here, it is more important for us to understand how it works. -- Regards, Alexander Borisov
