From b426e1b1fafdab688c646cef8245fa72403d37bb Mon Sep 17 00:00:00 2001 From: glass Date: Wed, 27 Nov 2013 16:07:10 +0000 Subject: * st.c (st_keys): define st_keys(). it writes each key to buffer. * hash.c (rb_hash_keys): use st_keys() for performance improvement if st_data_t and VALUE are compatible. * st.h: define macro ST_DATA_COMPATIBLE_P() to predicate whether st_data_t and passed type are compatible. * configure.in: check existence of builtin function to use in ST_DATA_COMPATIBLE_P(). git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/trunk@43885 b2dd03c8-39d4-4d8f-98ff-823fe69b080e --- ChangeLog | 13 +++++++++++++ configure.in | 2 ++ hash.c | 22 ++++++++++++++++++---- include/ruby/st.h | 8 ++++++++ st.c | 29 +++++++++++++++++++++++++++++ 5 files changed, 70 insertions(+), 4 deletions(-) diff --git a/ChangeLog b/ChangeLog index b075c25559..7ef43ffd02 100644 --- a/ChangeLog +++ b/ChangeLog @@ -1,3 +1,16 @@ +Thu Nov 28 00:36:52 2013 Masaki Matsushita + + * st.c (st_keys): define st_keys(). it writes each key to buffer. + + * hash.c (rb_hash_keys): use st_keys() for performance improvement + if st_data_t and VALUE are compatible. + + * st.h: define macro ST_DATA_COMPATIBLE_P() to predicate whether + st_data_t and passed type are compatible. + + * configure.in: check existence of builtin function to use in + ST_DATA_COMPATIBLE_P(). + Thu Nov 28 00:07:28 2013 Masaki Matsushita * ruby_atomic.h: remove duplicate definisions between ATOMIC_XXX diff --git a/configure.in b/configure.in index 1a6379cb4a..8bff18d6dd 100644 --- a/configure.in +++ b/configure.in @@ -1937,6 +1937,8 @@ RUBY_CHECK_BUILTIN_FUNC(__builtin_bswap64, [__builtin_bswap64(0)]) RUBY_CHECK_BUILTIN_FUNC(__builtin_clz, [__builtin_clz(0)]) RUBY_CHECK_BUILTIN_FUNC(__builtin_clzl, [__builtin_clzl(0)]) RUBY_CHECK_BUILTIN_FUNC(__builtin_clzll, [__builtin_clzll(0)]) +RUBY_CHECK_BUILTIN_FUNC(__builtin_choose_expr, [__builtin_choose_expr(0, 0, 0)]) +RUBY_CHECK_BUILTIN_FUNC(__builtin_types_compatible_p, [__builtin_types_compatible_p(int, int)]) # Some platform need -lrt for clock_gettime, but the other don't. if test x"$ac_cv_func_clock_gettime" != xyes; then diff --git a/hash.c b/hash.c index a114773259..4fc7b88668 100644 --- a/hash.c +++ b/hash.c @@ -1702,12 +1702,26 @@ keys_i(VALUE key, VALUE value, VALUE ary) VALUE rb_hash_keys(VALUE hash) { - VALUE ary; + VALUE keys; + int size = RHASH_SIZE(hash); - ary = rb_ary_new_capa(RHASH_SIZE(hash)); - rb_hash_foreach(hash, keys_i, ary); + keys = rb_ary_new_capa(size); + if (size == 0) return keys; - return ary; + if (ST_DATA_COMPATIBLE_P(VALUE)) { + st_table *table = RHASH(hash)->ntbl; + + if (OBJ_PROMOTED(keys)) rb_gc_writebarrier_remember_promoted(keys); + RARRAY_PTR_USE(keys, ptr, { + size = st_keys(table, ptr, size); + }); + rb_ary_set_len(keys, size); + } + else { + rb_hash_foreach(hash, keys_i, keys); + } + + return keys; } static int diff --git a/include/ruby/st.h b/include/ruby/st.h index e71301b519..fa6190dcd6 100644 --- a/include/ruby/st.h +++ b/include/ruby/st.h @@ -59,6 +59,13 @@ struct st_hash_type { #define ST_INDEX_BITS (sizeof(st_index_t) * CHAR_BIT) +#if defined(HAVE_BUILTIN___BUILTIN_CHOOSE_EXPR) && defined(HAVE_BUILTIN___BUILTIN_TYPES_COMPATIBLE_P) +# define ST_DATA_COMPATIBLE_P(type) \ + __builtin_choose_expr(__builtin_types_compatible_p(type, st_data_t), 1, 0) +#else +# define ST_DATA_COMPATIBLE_P(type) 0 +#endif + struct st_table { const struct st_hash_type *type; st_index_t num_bins; @@ -112,6 +119,7 @@ int st_update(st_table *table, st_data_t key, st_update_callback_func *func, st_ int st_foreach(st_table *, int (*)(ANYARGS), st_data_t); int st_foreach_check(st_table *, int (*)(ANYARGS), st_data_t, st_data_t); int st_reverse_foreach(st_table *, int (*)(ANYARGS), st_data_t); +st_index_t st_keys(st_table *table, st_data_t *keys, st_index_t size); void st_add_direct(st_table *, st_data_t, st_data_t); void st_free_table(st_table *); void st_cleanup_safe(st_table *, st_data_t); diff --git a/st.c b/st.c index c8f72c68c8..1fbf1f5e7c 100644 --- a/st.c +++ b/st.c @@ -1091,6 +1091,35 @@ st_foreach(st_table *table, int (*func)(ANYARGS), st_data_t arg) return 0; } +st_index_t +st_keys(st_table *table, st_data_t *keys, st_index_t size) +{ + st_data_t key, never = (st_data_t)Qundef; + st_data_t *keys_start = keys; + + if (table->entries_packed) { + st_index_t i; + + if (size > table->real_entries) size = table->real_entries; + for (i = 0; i < size; i++) { + key = PKEY(table, i); + if (key == never) continue; + *keys++ = key; + } + } + else { + st_table_entry *ptr = table->head; + st_data_t *keys_end = keys + size; + while (ptr && keys < keys_end) { + key = ptr->key; + if (key != never) *keys++ = key; + ptr = ptr->fore; + } + } + + return keys - keys_start; +} + #if 0 /* unused right now */ int st_reverse_foreach(st_table *table, int (*func)(ANYARGS), st_data_t arg) -- cgit v1.2.3