[gs-code-review] Fix : Replace packed_search_* macros with a
template.
Igor V. Melichev
igor.melichev at artifex.com
Mon Jun 18 14:11:12 PDT 2007
[Log message beg]
Fix : Replace packed_search_* macros with a template.
DETAILS :
This change is algorithmically equivalent.
It allows to trace through the packed search code
with Microsoft Developer Studio.
We define a new variable 'wrap'
for reducing 3 macros to a single template.
We believe it shouldn't cause a sensible slowdown.
An alternative is 2 (nested) templates and no new variables.
We noticed that the missing key case is not optimized well.
When the key is missing, the algorithm scans the
left part of the array 2 times. One time should be enough.
A possible optimization should be a separate patch,
rather it appears difficult in a single template with no code duplication.
EXPECTED DIFFERENCES :
None.
[Log message end]
-------------- next part --------------
*** F:\SVN-GS\HEAD\gs\src\idict.c Thu Jun 7 23:31:37 2007
--- files\gs\src\idict.c Tue Jun 19 00:53:32 2007
***************
*** 30,33 ****
--- 30,37 ----
#include "iutil.h"
#include "ivmspace.h" /* for store check */
+ /*
+ #include "idicttpl.h" - Do not remove this comment.
+ "idicttpl.h" is included below.
+ */
/*
***************
*** 340,349 ****
const ref_packed *pslot = 0;
! packed_search_1(*ppvalue = packed_search_value_pointer,
! return 1,
! if (pslot == 0) pslot = kp, goto miss);
! packed_search_2(*ppvalue = packed_search_value_pointer,
! return 1,
! if (pslot == 0) pslot = kp, goto miss);
/*
* Double wraparound, dict is full.
--- 344,354 ----
const ref_packed *pslot = 0;
! # define found *ppvalue = packed_search_value_pointer; return 1
! # define deleted if (pslot == 0) pslot = kp
! # define missing goto miss
! # include "idicttpl.h"
! # undef missing
! # undef deleted
! # undef found
/*
* Double wraparound, dict is full.
*** F:\SVN-GS\HEAD\gs\src\idictdef.h Thu Jun 7 23:31:53 2007
--- files\gs\src\idictdef.h Tue Jun 19 00:47:15 2007
***************
*** 80,117 ****
#define d_length(dct) ((uint)((dct)->count.value.intval))
! /*
! * Define macros for searching a packed dictionary. Free variables:
! * ref_packed kpack - holds the packed key.
! * uint hash - holds the hash of the name.
! * dict *pdict - points to the dictionary.
! * uint size - holds npairs(pdict).
! * Note that the macro is *not* enclosed in {}, so that we can access
! * the values of kbot and kp after leaving the loop.
! *
! * We break the macro into two to avoid overflowing some preprocessors.
! */
! /* packed_search_body also uses kp and kbot as free variables. */
#define packed_search_value_pointer (pdict->values.value.refs + (kp - kbot))
- #define packed_search_body(found1,found2,del,miss)\
- { if_debug2('D', "[D]probe 0x%lx: 0x%x\n", (ulong)kp, *kp);\
- if ( *kp == kpack )\
- { found1;\
- found2;\
- }\
- else if ( !r_packed_is_name(kp) )\
- { /* Empty, deleted, or wraparound. Figure out which. */\
- if ( *kp == packed_key_empty ) miss;\
- if ( kp == kbot ) break; /* wrap */\
- else { del; }\
- }\
- }
- #define packed_search_1(found1,found2,del,miss)\
- const ref_packed *kbot = pdict->keys.value.packed;\
- register const ref_packed *kp;\
- for ( kp = kbot + dict_hash_mod(hash, size) + 1; ; kp-- )\
- packed_search_body(found1,found2,del,miss)
- #define packed_search_2(found1,found2,del,miss)\
- for ( kp += size; ; kp-- )\
- packed_search_body(found1,found2,del,miss)
#endif /* idictdef_INCLUDED */
--- 80,86 ----
#define d_length(dct) ((uint)((dct)->count.value.intval))
! /* packed_search_value_pointer simplifies the access to
! packed dictionary search template data - see idicttpl.h . */
#define packed_search_value_pointer (pdict->values.value.refs + (kp - kbot))
#endif /* idictdef_INCLUDED */
*** F:\SVN-GS\HEAD\gs\src\idstack.c Thu Jun 7 23:31:40 2007
--- files\gs\src\idstack.c Tue Jun 19 01:06:47 2007
***************
*** 23,26 ****
--- 23,30 ----
#include "iutil.h"
#include "ivmspace.h"
+ /*
+ #include "idicttpl.h" - Do not remove this comment.
+ "idicttpl.h" is included below.
+ */
/* Debugging statistics */
***************
*** 124,134 ****
INCR(depth[min(MAX_STATS_DEPTH, pds->stack.p - pdref)])
if (dict_is_packed(pdict)) {
! packed_search_1(INCR_DEPTH(pdref),
! return packed_search_value_pointer,
! DO_NOTHING, goto miss);
! packed_search_2(INCR_DEPTH(pdref),
! return packed_search_value_pointer,
! DO_NOTHING, break);
! miss:;
} else {
/*
--- 128,138 ----
INCR(depth[min(MAX_STATS_DEPTH, pds->stack.p - pdref)])
if (dict_is_packed(pdict)) {
! # define found INCR_DEPTH(pdref); return packed_search_value_pointer
! # define deleted
! # define missing break;
! # include "idicttpl.h"
! # undef missing
! # undef deleted
! # undef found
} else {
/*
*** F:\SVN-GS\HEAD\gs\src\int.mak Thu Jun 7 23:31:18 2007
--- files\gs\src\int.mak Tue Jun 19 00:54:36 2007
***************
*** 53,56 ****
--- 53,57 ----
idict_h=$(PSSRC)idict.h $(iddstack_h)
idictdef_h=$(PSSRC)idictdef.h
+ idicttpl_h=$(PSSRC)idicttpl.h
idosave_h=$(PSSRC)idosave.h
igcstr_h=$(PSSRC)igcstr.h
***************
*** 169,173 ****
$(ierrors_h)\
$(gxalloc_h)\
! $(iddstack_h) $(idebug_h) $(idict_h) $(idictdef_h)\
$(imemory_h) $(iname_h) $(inamedef_h) $(ipacked_h) $(isave_h)\
$(iutil_h) $(ivmspace_h) $(store_h)
--- 170,174 ----
$(ierrors_h)\
$(gxalloc_h)\
! $(iddstack_h) $(idebug_h) $(idict_h) $(idictdef_h) $(idicttpl_h)\
$(imemory_h) $(iname_h) $(inamedef_h) $(ipacked_h) $(isave_h)\
$(iutil_h) $(ivmspace_h) $(store_h)
***************
*** 181,185 ****
$(PSOBJ)idstack.$(OBJ) : $(PSSRC)idstack.c $(GH)\
! $(idebug_h) $(idict_h) $(idictdef_h) $(idstack_h) $(iname_h) $(inamedef_h)\
$(ipacked_h) $(iutil_h) $(ivmspace_h)
$(PSCC) $(PSO_)idstack.$(OBJ) $(C_) $(PSSRC)idstack.c
--- 182,186 ----
$(PSOBJ)idstack.$(OBJ) : $(PSSRC)idstack.c $(GH)\
! $(idebug_h) $(idict_h) $(idictdef_h) $(idicttpl_h) $(idstack_h) $(iname_h) $(inamedef_h)\
$(ipacked_h) $(iutil_h) $(ivmspace_h)
$(PSCC) $(PSO_)idstack.$(OBJ) $(C_) $(PSSRC)idstack.c
-------------- next part --------------
/* Copyright (C) 2001-2006 Artifex Software, Inc.
All Rights Reserved.
This software is provided AS-IS with no warranty, either express or
implied.
This software is distributed under license and may not be copied, modified
or distributed except as expressly authorized under the terms of that
license. Refer to licensing information at http://www.artifex.com/
or contact Artifex Software, Inc., 7 Mt. Lassen Drive - Suite A-134,
San Rafael, CA 94903, U.S.A., +1(415)492-9861, for further information.
*/
/* $Id: idicttpl.h 8022 2007-06-05 22:23:38Z giles $ */
/* A template for packed dictionary search method */
/*
* Define template for searching a packed dictionary.
*
* Free variables:
* ref_packed kpack - holds the packed key.
* uint hash - holds the hash of the name.
* dict *pdict - points to the dictionary.
* uint size - holds npairs(pdict).
*
* Template parameters are :
* found - the found key action.
* deleted - the deleted key action.
* missing - the missed key action.
*
* Note that the template is *not* enclosed in {}, so that we can access
* the values of kbot and kp after leaving the template.
*/
const ref_packed *kbot = pdict->keys.value.packed;
register const ref_packed *kp = kbot + dict_hash_mod(hash, size) + 1;
int wrap = 0;
again:
for (; ; kp-- ) {
if_debug2('D', "[D]probe 0x%lx: 0x%x\n", (ulong)kp, *kp);
if ( *kp == kpack ) {
found;
} else if ( !r_packed_is_name(kp) ) {
/* Empty, deleted, or wraparound. Figure out which. */
if ( *kp == packed_key_empty )
missing;
if ( kp == kbot ) {
if (wrap)
break;
else {
wrap++;
kp += size; /* wrap */
goto again; /* skip "kp--". */
}
} else {
deleted;
}
}
}
More information about the gs-code-review
mailing list