#136 ./tool_dep_control/coarse_names and directory order
The ./tool_dep_control/coarse_names feature introduced in eval/91 seems to have a subtle problem that causes false cache misses.
The B type dependency which coarse_names uses includes not only the set of names in a directory, but also the order of those names. That order corresponds directly to the order of the name/value pairs in the binding in the evaluator when the tool starts. (Bindings are actually an ordered list of name/value pairs, not an unordered list like a hash table or list sorted by name.) Binding order can be affected by several things, including the order in which different bindings are combined with SDL operations like +, ++, and _append as well as the order of directory entries in immutable source versions.
When users are actively editing sources, the order of the directory entries in their source directories can change. This is especially true if they use an editor which deletes or renames the original file and creates a new one with the same name in its place. (Emacs does this, but vi does not.) This can cause cache misses for B type dependencies on any source directories brought in as a whole binding.
Using B type dependencies was convenient, but is a little too coarse in this case. It would be preferable to record a dependency on the set of names in a canonical (sorted) order rather than in whatever order the binding is in. I propose introducing a new dependency type which does this, possible using 'b' for its type character. Using such dependencies will have an additional computational overhead, but I think it will make ./tool_dep_control/coarse_names more useful.
Some people have asked whether we could generally eliminate the order that bindings have, but I don't think that's possible given that foreach and several primitive functions (_head, _tail, _elem, _sub) already expose the binding order to SDL code. Changing that would change the result of old builds, which is unacceptable.
As an aside, I should mention that one of the reasons this is an issue for us at Intel is that we have several tools which we don't have direct control over which generate temporary filenames and then search for those temporary filenames along a search path which includes the directories where the sources users edit directly from build to build are placed. Without using the ./tool_dep_control/coarse_names feature, this generates a large number of non-existence dependencies. As the temporary filenames vary from run to run, these can quickly accumulate creating a very large number of useless secondary dependencies in a single PKFile.
Logged In: YES
user_id=1144459
Originator: NO
Since listing directory depends on the order of names of the binding, sorted names dependency should be recorded only for lookup calls in the directory defined in tool_dep_control/coarse_names. But that does not seem to be enough for some tools we use in Intel. There was a suggestion to add another pragma to tool_dep_control so user could specify directory for which run_tool dependency should be recorded on sorted list of names for both lookup and list calls. But in that case shouldn’t we provide user with primitives to operate on sorted bindings?
Logged In: YES
user_id=291223
Originator: NO
There are plenty of times when sorting would be useful. If we implement it for bindings, we should probably support it for lists too. Of course that brings up the question of different sorting orders (case sensitive alpha, case insensitive alpha, numeric, etc).
For simplicity sake, I'd suggest we just start with a simple ASCII character code order as the only choice.
Logged In: YES
user_id=304837
Originator: YES
Here's another example of how binding sorting would be
useful: SDL code constructs a file with a list of filenames
(from the names in a binding) that is subsequently read by a
tool. (This actually describes production code at Intel.)
Currently this is sensitive to binding order. If there were
a _sort primitive the filename list file could be
constructed in a canonical order. One could imagine a
similar case for SDL that constructs a command line listing
multiple input files from the names in a binding.
Some initial testing with a new dependency type (see the
branch eval/93.sorted_names_dep) has turned up cases where
tools are listing directories and thus still showing
sensitivity to directory order. (When a tool makes calls
like readdir, it gets the directory names in the same order
as the binding that defines the directory.) That calls into
question the efficacy of the limited approach of recording
the dependencies for directories selected by
./tool_dep_control/coarse_names using a sorted order. I
think we should consider instead implementing a general
binding sort-by-name feature.
I'll go ahead and propose that we add:
_sort(b:binding)
We could add a second argument with a default value for
defining the sorting order:
def_binding_order(b1:binding,b2:binding):bool
{
return _n(b1) < _n(b2);
}
_sort(b:binding,
f:function(binding,binding):bool=def_binding_order)
(The function "def_binding_order" wouldn't actually be
accessible to SDL code, I'm just trying to illustrate how
the default behavior would work.)
For completeness we should also make the relative comparison
operators (<, <=, >, >=) work for text arguments.
Finally we could overload _sort for lists:
def_list_order(v1:any, v2:any): bool
{
return v1 < v2;
}
_sort(l:list,
f:function(any,any):bool=def_list_order)
With the addition of the _sort primitive function, an SDL
programmer working with a tool that's sensitive to directory
order (or that needs to use ./tool_dep_control/coarse_names
to avoid an explosion of useless secondary dependencies)
could simply use _sort on the necessary directories just
before calling _run_tool.