Re: Ping [PATCH V2] libcpp: Optimize #pragma once with a hash table [PR58770]

[Nathan Sidwell <nathan@acm.org>]

On 8/19/22 16:27, Paul Hollinsky wrote:
> Hi all,
> 
> Would love some feedback on this patch!
> 
> Thanks,
> Paul
> 
> On Mon, Aug 01, 2022 at 05:18:40AM +0000, Paul Hollinsky wrote:
>> Rather than traversing the all_files linked list for every include,
>> this factors out the quick idempotency checks (modification time
>> and size) to be the keys in a hash table so we can find matching
>> files quickly.

I'm probably confused, but why is the existing idempotency logic 
insufficiently optimal?  Can it be improved directly?

WRT using modification time as a key.  I don't see how that provides 
sufficient additional randomization to file size?  Groups of headers are 
often installed with the same mtime.

>>
>> The hash table value type is a linked list, in case more than one
>> file matches the quick check.
>>
>> The table is only built if a once-only file is seen, so include
>> guard performance is not affecte
>>
>> My laptop would previously complete Ricardo's benchmark from the
>> PR in ~1.1s using #pragma once, and ~0.35s using include guards.
>>
>> After this change, both benchmarks now complete in ~0.35s. I did
>> have to randomize the modification dates on the benchmark headers
>> so the files did not all end up in the same hash table list, but
>> that would likely not come up outside of the contrived benchmark.
>>
>> I bootstrapped and ran the testsuite on x86_64 Darwin, as well as
>> ppc64le and aarch64 Linux.
>>
>> libcpp/ChangeLog:
>>
>> 	PR preprocessor/58770
>> 	* internal.h: Add hash table for #pragma once
>> 	* files.cc: Optimize #pragma once with the hash table
>>
>> Signed-off-by: Paul Hollinsky <paulhollinsky@gmail.com>
>> ---
>>   libcpp/files.cc   | 116 +++++++++++++++++++++++++++++++++++++++++++---
>>   libcpp/internal.h |   3 ++
>>   2 files changed, 112 insertions(+), 7 deletions(-)
>>
>> diff --git a/libcpp/files.cc b/libcpp/files.cc
>> index 24208f7b0f8..d4ffd77578e 100644
>> --- a/libcpp/files.cc
>> +++ b/libcpp/files.cc
>> @@ -167,6 +167,33 @@ struct file_hash_entry_pool
>>     struct cpp_file_hash_entry pool[FILE_HASH_POOL_SIZE];
>>   };
>>   
>> +/* A set of attributes designed to quickly identify obviously different files
>> +   in a hashtable.  Just in case there are collisions, we still maintain a
>> +   list.  These sub-lists can then be checked for #pragma once rather than
>> +   interating through all_files.  */
>> +struct file_quick_idempotency_attrs
>> +{
>> +  file_quick_idempotency_attrs(const _cpp_file *f)
>> +    : mtime(f->st.st_mtime), size(f->st.st_size) {}
>> +
>> +  time_t mtime;
>> +  off_t size;
>> +
>> +  static hashval_t hash (/* _cpp_file* */ const void *p);
>> +};
>> +
>> +/* Sub-list of very similar files kept in a hashtable to check for #pragma
>> +   once.  */
>> +struct file_sublist
>> +{
>> +  _cpp_file *f;
>> +  file_sublist *next;
>> +
>> +  static int eq (/* _cpp_file* */ const void *p,
>> +		 /* file_sublist* */ const void *q);
>> +  static void del (/* file_sublist* */ void *p);
>> +};
>> +
>>   static bool open_file (_cpp_file *file);
>>   static bool pch_open_file (cpp_reader *pfile, _cpp_file *file,
>>   			   bool *invalid_pch);
>> @@ -849,17 +876,17 @@ has_unique_contents (cpp_reader *pfile, _cpp_file *file, bool import,
>>     if (!pfile->seen_once_only)
>>       return true;
>>   
>> -  /* We may have read the file under a different name.  Look
>> -     for likely candidates and compare file contents to be sure.  */
>> -  for (_cpp_file *f = pfile->all_files; f; f = f->next_file)
>> +  /* We may have read the file under a different name.  We've kept
>> +     similar looking files in this lists under this hash table, so
>> +     check those more thoroughly.  */
>> +  void* ent = htab_find(pfile->pragma_once_files, file);
>> +  for (file_sublist *e = static_cast<file_sublist *> (ent); e; e = e->next)
>>       {
>> +      _cpp_file *f = e->f;
>>         if (f == file)
>>   	continue; /* It'sa me!  */
>>   
>> -      if ((import || f->once_only)
>> -	  && f->err_no == 0
>> -	  && f->st.st_mtime == file->st.st_mtime
>> -	  && f->st.st_size == file->st.st_size)
>> +      if ((import || f->once_only) && f->err_no == 0)
>>   	{
>>   	  _cpp_file *ref_file;
>>   
>> @@ -895,6 +922,38 @@ has_unique_contents (cpp_reader *pfile, _cpp_file *file, bool import,
>>     return true;
>>   }
>>   
>> +/* Add the given file to the #pragma once table so it can be
>> +   quickly identified and excluded the next time it's seen.  */
>> +static void
>> +update_pragma_once_table (cpp_reader *pfile, _cpp_file *file)
>> +{
>> +  void **slot = htab_find_slot (pfile->pragma_once_files, file, INSERT);
>> +  if (slot)
>> +    {
>> +      if (!*slot)
>> +	*slot = xcalloc (1, sizeof (file_sublist));
>> +
>> +      file_sublist *e = static_cast<file_sublist *> (*slot);
>> +      while (e->f)
>> +	{
>> +	  if (!e->next)
>> +	    {
>> +	      void *new_sublist = xcalloc(1, sizeof (file_sublist));
>> +	      e->next = static_cast<file_sublist *> (new_sublist);
>> +	    }
>> +	  e = e->next;
>> +	}
>> +
>> +      e->f = file;
>> +    }
>> +  else
>> +    {
>> +      cpp_error (pfile, CPP_DL_ERROR,
>> +		 "Unable to create #pragma once table space for %s",
>> +		 _cpp_get_file_name (file));
>> +    }
>> +}
>> +
>>   /* Place the file referenced by FILE into a new buffer on the buffer
>>      stack if possible.  Returns true if a buffer is stacked.  Use LOC
>>      for any diagnostics.  */
>> @@ -950,6 +1009,9 @@ _cpp_stack_file (cpp_reader *pfile, _cpp_file *file, include_type type,
>>         if (!has_unique_contents (pfile, file, type == IT_IMPORT, loc))
>>   	return false;
>>   
>> +      if (pfile->seen_once_only && file->once_only)
>> +	update_pragma_once_table (pfile, file);
>> +
>>         if (pfile->buffer && file->dir)
>>   	sysp = MAX (pfile->buffer->sysp, file->dir->sysp);
>>   
>> @@ -1434,6 +1496,41 @@ nonexistent_file_hash_eq (const void *p, const void *q)
>>     return filename_cmp ((const char *) p, (const char *) q) == 0;
>>   }
>>   
>> +/* Hasher for the #pragma once hash table.  */
>> +hashval_t
>> +file_quick_idempotency_attrs::hash (const void *p)
>> +{
>> +  const _cpp_file *f = static_cast<const _cpp_file *> (p);
>> +  file_quick_idempotency_attrs kh (f);
>> +  return iterative_hash_object (kh, 0);
>> +}
>> +
>> +/* Equality checker for the #pragma once hash table.  */
>> +int
>> +file_sublist::eq (const void *p, const void *q)
>> +{
>> +  /* Just check if the file q would be in the list p. Every
>> +     file in the list should have these attributes the same,
>> +     so we don't need to traverse.  */
>> +  const file_sublist *e = static_cast<const file_sublist *> (p);
>> +  const _cpp_file *f = static_cast<const _cpp_file *> (q);
>> +  return f->st.st_mtime == e->f->st.st_mtime
>> +	 && f->st.st_size == e->f->st.st_size;
>> +}
>> +
>> +/* Cleanup for a file sub-list. Does not free the _cpp_file
>> +   structures within.  */
>> +void
>> +file_sublist::del (void *p)
>> +{
>> +  file_sublist *e = static_cast<file_sublist *> (p);
>> +  if (e->next)
>> +    {
>> +      file_sublist::del (e->next);
>> +      free (e->next);
>> +    }
>> +}
>> +
>>   /* Initialize everything in this source file.  */
>>   void
>>   _cpp_init_files (cpp_reader *pfile)
>> @@ -1442,6 +1539,10 @@ _cpp_init_files (cpp_reader *pfile)
>>   					NULL, xcalloc, free);
>>     pfile->dir_hash = htab_create_alloc (127, file_hash_hash, file_hash_eq,
>>   					NULL, xcalloc, free);
>> +  pfile->pragma_once_files = htab_create_alloc (127,
>> +					file_quick_idempotency_attrs::hash,
>> +					file_sublist::eq, file_sublist::del,
>> +					xcalloc, free);
>>     allocate_file_hash_entries (pfile);
>>     pfile->nonexistent_file_hash = htab_create_alloc (127, htab_hash_string,
>>   						    nonexistent_file_hash_eq,
>> @@ -1456,6 +1557,7 @@ _cpp_cleanup_files (cpp_reader *pfile)
>>   {
>>     htab_delete (pfile->file_hash);
>>     htab_delete (pfile->dir_hash);
>> +  htab_delete (pfile->pragma_once_files);
>>     htab_delete (pfile->nonexistent_file_hash);
>>     obstack_free (&pfile->nonexistent_file_ob, 0);
>>     free_file_hash_entries (pfile);
>> diff --git a/libcpp/internal.h b/libcpp/internal.h
>> index badfd1b40da..9c3c46df335 100644
>> --- a/libcpp/internal.h
>> +++ b/libcpp/internal.h
>> @@ -485,6 +485,9 @@ struct cpp_reader
>>        been used.  */
>>     bool seen_once_only;
>>   
>> +  /* Optimization for #pragma once.  */
>> +  struct htab *pragma_once_files;
>> +
>>     /* Multiple include optimization.  */
>>     const cpp_hashnode *mi_cmacro;
>>     const cpp_hashnode *mi_ind_cmacro;
>> -- 
>> 2.34.1
>>


-- 
Nathan Sidwell