This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
Re: PATCH: Speed up G++
- From: Nathan Sidwell <nathan at codesourcery dot com>
- To: mark at codesourcery dot com
- Cc: gcc-patches at gcc dot gnu dot org
- Date: Thu, 08 Jul 2004 10:42:20 +0100
- Subject: Re: PATCH: Speed up G++
- Organization: Codesourcery LLC
- References: <200407080439.i684dfPo001827@sirius.codesourcery.com>
Mark Mitchell wrote:
Nathan, I broke the vector abstraction barrier in push_binding, where
I calculate "need_fixup". You will want to go back and adjust that
code after you add the additional vector API function we dicussed
today.
Fixed & installed thusly. The allocation functions now take a signed
value where >= 0 means exact and <0 means at least 1, but increae
exponentially. One exception is the default explicit allocator, for
which 0 also means default.
built & tested on i686-pc-linux-gnu.
nathan
--
Nathan Sidwell :: http://www.codesourcery.com :: CodeSourcery LLC
nathan@codesourcery.com :: http://www.planetfall.pwp.blueyonder.co.uk
2004-07-08 Nathan Sidwell <nathan@codesourcery.com>
* vec.c (vec_p_reserve, vec_o_reserve): Allocation is signed.
* vec.h (VEC_alloc, VEC_embedded_size, VEC_embedded_init):
Allocation is signed.
(VEC_reserve): Return flag, allocation is signed.
2004-07-08 Nathan Sidwell <nathan@codesourcery.com>
* name-lookup.c (push_binding): Use VEC_reserve.
Index: vec.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/vec.c,v
retrieving revision 2.2
diff -c -3 -p -r2.2 vec.c
*** vec.c 6 Jul 2004 17:08:42 -0000 2.2
--- vec.c 8 Jul 2004 09:36:57 -0000
*************** struct vec_prefix
*** 34,77 ****
void *vec[1];
};
! /* Ensure there are at least RESERVE free slots in VEC, if RESERVE !=
! ~0u. If RESERVE == ~0u increase the current allocation
! exponentially. VEC can be NULL, to create a new vector. */
void *
! vec_p_reserve (void *vec, size_t reserve MEM_STAT_DECL)
{
return vec_o_reserve (vec, reserve,
offsetof (struct vec_prefix, vec), sizeof (void *)
PASS_MEM_STAT);
}
! /* Ensure there are at least RESERVE free slots in VEC, if RESERVE !=
! ~0u. If RESERVE == ~0u, increase the current allocation
! exponentially. VEC can be NULL, in which case a new vector is
! created. The vector's trailing array is at VEC_OFFSET offset and
! consistes of ELT_SIZE sized elements. */
void *
! vec_o_reserve (void *vec, size_t reserve, size_t vec_offset, size_t elt_size
MEM_STAT_DECL)
{
struct vec_prefix *pfx = vec;
! size_t alloc;
! if (reserve + 1)
! alloc = (pfx ? pfx->num : 0) + reserve;
else
! alloc = pfx ? pfx->alloc * 2 : 4;
! if (!pfx || pfx->alloc < alloc)
! {
! vec = ggc_realloc_stat (vec, vec_offset + alloc * elt_size
! PASS_MEM_STAT);
! ((struct vec_prefix *)vec)->alloc = alloc;
! if (!pfx)
! ((struct vec_prefix *)vec)->num = 0;
! }
return vec;
}
--- 34,78 ----
void *vec[1];
};
! /* Ensure there are at least RESERVE free slots in VEC, if RESERVE >=
! 0. If RESERVE < 0 increase the current allocation exponentially.
! VEC can be NULL, to create a new vector. */
void *
! vec_p_reserve (void *vec, int reserve MEM_STAT_DECL)
{
return vec_o_reserve (vec, reserve,
offsetof (struct vec_prefix, vec), sizeof (void *)
PASS_MEM_STAT);
}
! /* Ensure there are at least RESERVE free slots in VEC, if RESERVE >=
! 0. If RESERVE < 0, increase the current allocation exponentially.
! VEC can be NULL, in which case a new vector is created. The
! vector's trailing array is at VEC_OFFSET offset and consistes of
! ELT_SIZE sized elements. */
void *
! vec_o_reserve (void *vec, int reserve, size_t vec_offset, size_t elt_size
MEM_STAT_DECL)
{
struct vec_prefix *pfx = vec;
! size_t alloc = pfx ? pfx->num : 0;
! if (reserve >= 0)
! alloc += reserve;
! else if (alloc)
! alloc *= 2;
else
! alloc = 4;
!
! if (pfx && pfx->alloc >= alloc)
! abort ();
! vec = ggc_realloc_stat (vec, vec_offset + alloc * elt_size PASS_MEM_STAT);
! ((struct vec_prefix *)vec)->alloc = alloc;
! if (!pfx)
! ((struct vec_prefix *)vec)->num = 0;
return vec;
}
Index: vec.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/vec.h,v
retrieving revision 2.5
diff -c -3 -p -r2.5 vec.h
*** vec.h 7 Jul 2004 08:25:04 -0000 2.5
--- vec.h 8 Jul 2004 09:36:58 -0000
*************** Software Foundation, 59 Temple Place - S
*** 58,64 ****
vector, if needed. Reallocation causes an exponential increase in
vector size. If you know you will be adding N elements, it would
be more efficient to use the reserve operation before adding the
! elements with the 'quick' operation.
You should prefer the push and pop operations, as they append and
remove from the end of the vector. If you need to remove several
--- 58,66 ----
vector, if needed. Reallocation causes an exponential increase in
vector size. If you know you will be adding N elements, it would
be more efficient to use the reserve operation before adding the
! elements with the 'quick' operation. You may also use the reserve
! operation with a -1 operand, to gain control over exactly when
! reallocation occurs.
You should prefer the push and pop operations, as they append and
remove from the end of the vector. If you need to remove several
*************** Software Foundation, 59 Temple Place - S
*** 132,158 ****
#define VEC_iterate(TDEF,V,I) (VEC_OP(TDEF,iterate)(V,I))
/* Allocate new vector.
! VEC(T) *VEC_T_alloc(size_t reserve);
! Allocate a new vector with space for RESERVE objects. */
#define VEC_alloc(TDEF,A) (VEC_OP(TDEF,alloc)(A MEM_STAT_INFO))
/* Use these to determine the required size and initialization of a
vector embedded within another structure (as the final member).
! size_t VEC_T_embedded_size(size_t reserve);
! void VEC_T_embedded_init(VEC(T) *v, size_t reserve);
These allow the caller to perform the memory allocation. */
#define VEC_embedded_size(TDEF,A) (VEC_OP(TDEF,embedded_size)(A))
#define VEC_embedded_init(TDEF,O,A) (VEC_OP(TDEF,embedded_init)(O,A))
/* Reserve space.
! void VEC_T_reserve(VEC(T) *&v, size_t reserve);
! Ensure that V has at least RESERVE slots available. Note this can
! cause V to be reallocated. */
! #define VEC_reserve(TDEF,V,R) (VEC_OP(TDEF,reserve)(&(V),R MEM_STAT_INFO))
/* Push object with no reallocation
T *VEC_T_quick_push (VEC(T) *v, T obj); // Pointer
--- 134,166 ----
#define VEC_iterate(TDEF,V,I) (VEC_OP(TDEF,iterate)(V,I))
/* Allocate new vector.
! VEC(T) *VEC_T_alloc(int reserve);
! Allocate a new vector with space for RESERVE objects. If RESERVE
! is <= 0, a default number of slots are created. */
#define VEC_alloc(TDEF,A) (VEC_OP(TDEF,alloc)(A MEM_STAT_INFO))
/* Use these to determine the required size and initialization of a
vector embedded within another structure (as the final member).
! size_t VEC_T_embedded_size(int reserve);
! void VEC_T_embedded_init(VEC(T) *v, int reserve);
These allow the caller to perform the memory allocation. */
#define VEC_embedded_size(TDEF,A) (VEC_OP(TDEF,embedded_size)(A))
#define VEC_embedded_init(TDEF,O,A) (VEC_OP(TDEF,embedded_init)(O,A))
/* Reserve space.
! int VEC_T_reserve(VEC(T) *&v, int reserve);
! Ensure that V has at least RESERVE slots available, if RESERVE is
! >= 0. If RESERVE < 0, ensure that there is at least one spare
! slot. These differ in their reallocation behaviour, the first will
! not create additionsl headroom, but the second mechanism will
! perform the usual exponential headroom increase. Note this can
! cause V to be reallocated. Returns non-zero iff reallocation
! actually occurred. */
! #define VEC_reserve(TDEF,V,R) (VEC_OP(TDEF,reserve)(&(V),R MEM_STAT_INFO))
/* Push object with no reallocation
T *VEC_T_quick_push (VEC(T) *v, T obj); // Pointer
*************** Software Foundation, 59 Temple Place - S
*** 238,245 ****
#if !IN_GENGTYPE
/* Reallocate an array of elements with prefix. */
! extern void *vec_p_reserve (void *, size_t MEM_STAT_DECL);
! extern void *vec_o_reserve (void *, size_t, size_t, size_t MEM_STAT_DECL);
#if ENABLE_CHECKING
extern void vec_assert_fail (const char *, const char *,
--- 246,253 ----
#if !IN_GENGTYPE
/* Reallocate an array of elements with prefix. */
! extern void *vec_p_reserve (void *, int MEM_STAT_DECL);
! extern void *vec_o_reserve (void *, int, size_t, size_t MEM_STAT_DECL);
#if ENABLE_CHECKING
extern void vec_assert_fail (const char *, const char *,
*************** static inline TDEF VEC_OP (TDEF,iterate)
*** 310,337 ****
} \
\
static inline VEC (TDEF) *VEC_OP (TDEF,alloc MEM_STAT_DECL) \
! (size_t alloc_) \
{ \
return vec_p_reserve (NULL, alloc_ - !alloc_ PASS_MEM_STAT); \
} \
\
static inline size_t VEC_OP (TDEF,embedded_size) \
! (size_t alloc_) \
{ \
return offsetof (VEC(TDEF),vec) + alloc_ * sizeof(TDEF); \
} \
\
static inline void VEC_OP (TDEF,embedded_init) \
! (VEC (TDEF) *vec_, size_t alloc_) \
{ \
vec_->num = 0; \
vec_->alloc = alloc_; \
} \
\
! static inline void VEC_OP (TDEF,reserve) \
! (VEC (TDEF) **vec_, size_t alloc_ MEM_STAT_DECL) \
{ \
! *vec_ = vec_p_reserve (*vec_, alloc_ PASS_MEM_STAT); \
} \
\
static inline TDEF *VEC_OP (TDEF,quick_push) \
--- 318,351 ----
} \
\
static inline VEC (TDEF) *VEC_OP (TDEF,alloc MEM_STAT_DECL) \
! (int alloc_) \
{ \
return vec_p_reserve (NULL, alloc_ - !alloc_ PASS_MEM_STAT); \
} \
\
static inline size_t VEC_OP (TDEF,embedded_size) \
! (int alloc_) \
{ \
return offsetof (VEC(TDEF),vec) + alloc_ * sizeof(TDEF); \
} \
\
static inline void VEC_OP (TDEF,embedded_init) \
! (VEC (TDEF) *vec_, int alloc_) \
{ \
vec_->num = 0; \
vec_->alloc = alloc_; \
} \
\
! static inline int VEC_OP (TDEF,reserve) \
! (VEC (TDEF) **vec_, int alloc_ MEM_STAT_DECL) \
{ \
! int extend = !*vec_ || ((*vec_)->alloc - (*vec_)->num \
! < (size_t)(alloc_ < 0 ? 1 : alloc_)); \
! \
! if (extend) \
! *vec_ = vec_p_reserve (*vec_, alloc_ PASS_MEM_STAT); \
! \
! return extend; \
} \
\
static inline TDEF *VEC_OP (TDEF,quick_push) \
*************** static inline TDEF *VEC_OP (TDEF,quick_p
*** 349,356 ****
static inline TDEF *VEC_OP (TDEF,safe_push) \
(VEC (TDEF) **vec_, TDEF obj_ MEM_STAT_DECL) \
{ \
! if (!*vec_ || (*vec_)->num == (*vec_)->alloc) \
! VEC_OP (TDEF,reserve) (vec_, ~(size_t)0 PASS_MEM_STAT); \
\
return VEC_OP (TDEF,quick_push) (*vec_, obj_); \
} \
--- 363,369 ----
static inline TDEF *VEC_OP (TDEF,safe_push) \
(VEC (TDEF) **vec_, TDEF obj_ MEM_STAT_DECL) \
{ \
! VEC_OP (TDEF,reserve) (vec_, -1 PASS_MEM_STAT); \
\
return VEC_OP (TDEF,quick_push) (*vec_, obj_); \
} \
*************** static inline TDEF *VEC_OP (TDEF,quick_i
*** 402,409 ****
static inline TDEF *VEC_OP (TDEF,safe_insert) \
(VEC (TDEF) **vec_, size_t ix_, TDEF obj_ MEM_STAT_DECL) \
{ \
! if (!*vec_ || (*vec_)->num == (*vec_)->alloc) \
! VEC_OP (TDEF,reserve) (vec_, ~(size_t)0 PASS_MEM_STAT); \
\
return VEC_OP (TDEF,quick_insert) (*vec_, ix_, obj_); \
} \
--- 415,421 ----
static inline TDEF *VEC_OP (TDEF,safe_insert) \
(VEC (TDEF) **vec_, size_t ix_, TDEF obj_ MEM_STAT_DECL) \
{ \
! VEC_OP (TDEF,reserve) (vec_, -1 PASS_MEM_STAT); \
\
return VEC_OP (TDEF,quick_insert) (*vec_, ix_, obj_); \
} \
*************** static inline TDEF *VEC_OP (TDEF,iterate
*** 476,482 ****
} \
\
static inline VEC (TDEF) *VEC_OP (TDEF,alloc) \
! (size_t alloc_ MEM_STAT_DECL) \
{ \
return vec_o_reserve (NULL, alloc_ - !alloc_, \
offsetof (VEC(TDEF),vec), sizeof (TDEF) \
--- 488,494 ----
} \
\
static inline VEC (TDEF) *VEC_OP (TDEF,alloc) \
! (int alloc_ MEM_STAT_DECL) \
{ \
return vec_o_reserve (NULL, alloc_ - !alloc_, \
offsetof (VEC(TDEF),vec), sizeof (TDEF) \
*************** static inline VEC (TDEF) *VEC_OP (TDEF,a
*** 484,507 ****
} \
\
static inline size_t VEC_OP (TDEF,embedded_size) \
! (size_t alloc_) \
{ \
return offsetof (VEC(TDEF),vec) + alloc_ * sizeof(TDEF); \
} \
\
static inline void VEC_OP (TDEF,embedded_init) \
! (VEC (TDEF) *vec_, size_t alloc_) \
{ \
vec_->num = 0; \
vec_->alloc = alloc_; \
} \
\
! static inline void VEC_OP (TDEF,reserve) \
! (VEC (TDEF) **vec_, size_t alloc_ MEM_STAT_DECL) \
{ \
! *vec_ = vec_o_reserve (*vec_, alloc_, \
! offsetof (VEC(TDEF),vec), sizeof (TDEF) \
! PASS_MEM_STAT); \
} \
\
static inline TDEF *VEC_OP (TDEF,quick_push) \
--- 496,525 ----
} \
\
static inline size_t VEC_OP (TDEF,embedded_size) \
! (int alloc_) \
{ \
return offsetof (VEC(TDEF),vec) + alloc_ * sizeof(TDEF); \
} \
\
static inline void VEC_OP (TDEF,embedded_init) \
! (VEC (TDEF) *vec_, int alloc_) \
{ \
vec_->num = 0; \
vec_->alloc = alloc_; \
} \
\
! static inline int VEC_OP (TDEF,reserve) \
! (VEC (TDEF) **vec_, int alloc_ MEM_STAT_DECL) \
{ \
! int extend = !*vec_ || ((*vec_)->alloc - (*vec_)->num \
! < (size_t)(alloc_ < 0 ? 1 : alloc_)); \
! \
! if (extend) \
! *vec_ = vec_o_reserve (*vec_, alloc_, \
! offsetof (VEC(TDEF),vec), sizeof (TDEF) \
! PASS_MEM_STAT); \
! \
! return extend; \
} \
\
static inline TDEF *VEC_OP (TDEF,quick_push) \
*************** static inline TDEF *VEC_OP (TDEF,quick_p
*** 520,527 ****
static inline TDEF *VEC_OP (TDEF,safe_push) \
(VEC (TDEF) **vec_, const TDEF *obj_ MEM_STAT_DECL) \
{ \
! if (!*vec_ || (*vec_)->num == (*vec_)->alloc) \
! VEC_OP (TDEF,reserve) (vec_, ~(size_t)0 PASS_MEM_STAT); \
\
return VEC_OP (TDEF,quick_push) (*vec_, obj_); \
} \
--- 538,544 ----
static inline TDEF *VEC_OP (TDEF,safe_push) \
(VEC (TDEF) **vec_, const TDEF *obj_ MEM_STAT_DECL) \
{ \
! VEC_OP (TDEF,reserve) (vec_, -1 PASS_MEM_STAT); \
\
return VEC_OP (TDEF,quick_push) (*vec_, obj_); \
} \
*************** static inline TDEF *VEC_OP (TDEF,quick_i
*** 571,578 ****
static inline TDEF *VEC_OP (TDEF,safe_insert) \
(VEC (TDEF) **vec_, size_t ix_, const TDEF *obj_ MEM_STAT_DECL) \
{ \
! if (!*vec_ || (*vec_)->num == (*vec_)->alloc) \
! VEC_OP (TDEF,reserve) (vec_, ~(size_t)0 PASS_MEM_STAT); \
\
return VEC_OP (TDEF,quick_insert) (*vec_, ix_, obj_); \
} \
--- 588,594 ----
static inline TDEF *VEC_OP (TDEF,safe_insert) \
(VEC (TDEF) **vec_, size_t ix_, const TDEF *obj_ MEM_STAT_DECL) \
{ \
! VEC_OP (TDEF,reserve) (vec_, -1 PASS_MEM_STAT); \
\
return VEC_OP (TDEF,quick_insert) (*vec_, ix_, obj_); \
} \
Index: cp/name-lookup.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/cp/name-lookup.c,v
retrieving revision 1.67
diff -c -3 -p -r1.67 name-lookup.c
*** cp/name-lookup.c 8 Jul 2004 04:32:27 -0000 1.67
--- cp/name-lookup.c 8 Jul 2004 09:37:08 -0000
*************** push_binding (tree id, tree decl, cxx_sc
*** 381,402 ****
else
{
cp_class_binding *cb;
- size_t length;
- size_t i;
- bool need_fixup;
! length = VEC_length (cp_class_binding, level->class_shadowed);
! need_fixup = (length && length == level->class_shadowed->alloc);
! cb = VEC_safe_push (cp_class_binding, level->class_shadowed, NULL);
cb->identifier = id;
binding = &cb->base;
cxx_binding_init (binding, decl, NULL_TREE);
- if (need_fixup)
- for (i = 0; i < length; ++i)
- {
- cb = VEC_index (cp_class_binding, level->class_shadowed, i);
- IDENTIFIER_BINDING (cb->identifier) = &cb->base;
- }
}
/* Now, fill in the binding information. */
--- 381,402 ----
else
{
cp_class_binding *cb;
! if (VEC_reserve (cp_class_binding, level->class_shadowed, -1))
! {
! /* Fixup the current bindings, as they might have moved. */
! size_t i;
!
! for (i = 0;
! (cb = VEC_iterate (cp_class_binding, level->class_shadowed, i));
! i++)
! IDENTIFIER_BINDING (cb->identifier) = &cb->base;
! }
!
! cb = VEC_quick_push (cp_class_binding, level->class_shadowed, NULL);
cb->identifier = id;
binding = &cb->base;
cxx_binding_init (binding, decl, NULL_TREE);
}
/* Now, fill in the binding information. */