Making "is_a?" Fast

Transcript

1. John Hawthorn - RubyConf mini 2022 Making is_a? Fast
2. • Ruby Core Team • Rails Core Team • Sta ff Engineer @ GitHub John Hawthorn @jhawthorn @jhawthorn@ruby.social he/him
3. is_a? "Is this object of this class/module"
4. "foo".is_a?(String) => true "foo".is_a?(Integer) => false 123.is_a?(Integer) => true 123.is_a?(Numeric) => true
6. is_a?(Pigeon) Making is_a? Fast #<Butterfly:0x00 00000104e436d0>
7. String === x x.is_a?(String)
8. • kind_of? • Module#=== • case statement • rescue statement • protected methods What is "is_a?" is_a?("is_a?")
9. 2% of total Ruby runtime* is_a? * In Rails apps I measured, your mileage may vary
10. Profiling Ruby stackprof or rbspy
11. $ stackprof benchmarks/railsbench/out.bench ================================== Mode: wall(1000) Samples: 32453 (0.00% miss rate) GC: 3699 (11.40%) ================================== TOTAL (pct) SAMPLES (pct) FRAME 1646 (5.1%) 1646 (5.1%) String#gsub! 2295 (7.1%) 698 (2.2%) Class#new 1375 (4.2%) 654 (2.0%) Jbuilder#_set_value 1139 (3.5%) 637 (2.0%) ActiveModel::Type::Hel 565 (1.7%) 565 (1.7%) Module#=== 554 (1.7%) 554 (1.7%) JSON::Ext::Generator::
12. $ stackprof redacted_2022-11-02-14-23-11.stackprof.json ================================== Mode: wall(200) Samples: 64246 (4.57% miss rate) GC: 0 (0.00%) ================================== TOTAL (pct) SAMPLES (pct) FRAME 4725 (7.4%) 4725 (7.4%) IO#read 14203 (22.1%) 3278 (5.1%) Class#new 2513 (3.9%) 2513 (3.9%) Kernel#is_a? 2380 (3.7%) 2307 (3.6%) Trilogy#query
13. Profiling C perf https://www.brendangregg.com/perf.html https://perf.wiki.kernel.org/index.php/Main_Page
16. rb_define_method(rb_mKernel, "kind_of?", rb_obj_is_kind_of, 1); rb_define_method(rb_mKernel, "is_a?", rb_obj_is_kind_of, 1); rb_obj_is_kind_of src/ruby/object.c VALUE rb_obj_is_kind_of(VALUE obj, VALUE c);
17. bool rb_obj_is_kind_of(VALUE obj, VALUE search) { return class_search_ancestor(CLASS_OF(obj), search); }
18. bool class_search_ancestor(VALUE cl, VALUE search) { while (cl) { if (cl == c) return true; cl = RCLASS_SUPER(cl); } return false; } bool rb_obj_is_kind_of(VALUE obj, VALUE search) { return class_search_ancestor(CLASS_OF(obj), search); }
19. def class_search_ancestor(klass, search) while klass return true if klass == search klass = klass.superclass end false end def rb_obj_is_kind_of(obj, search) class_search_ancestor(obj.class, search) end
20. Butter fl y Object BasicObject Pidgeon
21. Butter fl y Object BasicObject Pidgeon
22. Butter fl y Object BasicObject Pidgeon
23. Butter fl y Object BasicObject
24. Butter fl y Object BasicObject
25. Butter fl y Object BasicObject ICLASS ICLASS
26. Butter fl y Object BasicObject ICLASS ICLASS
27. Butter fl y Object PP::ObjectMixin Kernel BasicObject ICLASS ICLASS
28. rb_obj_is_kind_of(obj, klass) def class_search_superclass(klass, search) while klass return true if klass == search klass = klass.superclass end false end def rb_obj_is_kind_of(obj, search) class_search_superclass(obj.class, search) end
29. rb_obj_is_kind_of(obj, klass) def class_search_superclass(klass, search) while klass return true if klass == search klass = klass.superclass end false end def rb_obj_is_kind_of(obj, search) class_search_superclass(obj.class, search) end ObjectSpace.internal_super_of ObjectSpace.internal_class_of
30. rb_obj_is_kind_of(obj, klass) def class_search_superclass(klass, search) while klass return true if klass == search klass = ObjectSpace.internal_super_of(klass) end false end def rb_obj_is_kind_of(obj, search) class_search_superclass(ObjectSpace.internal_class_of(class), sea end
31. Butter fl y Object PP::ObjectMixin Kernel BasicObject ICLASS ICLASS CPU 😢 • cache lines • branch prediction
32. klass klass.ancestors.size Object 11 Hash 19 Array 21 String 19 ActiveRecord::Base 72 ApplicationRecord::Base 80 ApplicationController 129 Repository 271 Organization 305
33. What to do? Avoid is_a? - use instance_of? Simplify class hierarchy Improve is_a? Avoid is_a? - respond_to?
34. Library/Framework Application Where to fix? Language Easy to change Hard to change Narrow fi x Broad fi x
35. Let's fix it in CRuby
36. Hash table Attempt #1
37. hash = { Pidgeon => true, Object => true, PP::ObjectMixin => true, Kernel => true, BasicObject => true } # to test hash.include?(klass)
38. def build_class_table(klass) hash = {} while klass hash[klass] = true klass = klass.super end hash end # to test hash.include?(klass)
39. st_table *build_class_table(VALUE klass) { st_table *hash = st_build_numtable(); while (klass) { st_insert(hash, klass, Qtrue); klass = RCLASS_SUPER(klass); } return hash; } // to test st_lookup(hash, klass, NULL)
43. 🫤 Complex 🫤 Needs cache invalidation 🫤 Slower in best case 🫤 Lots of memory used ✅ Consistent performance ✅ Faster in worst case
44. Attempt #2
45. bool class_search_ancestor(VALUE cl, VALUE search) { rb_obj_info_dump(search); while (cl) { if (cl == search) return true; cl = RCLASS_SUPER(cl); } return false; }
46. 849127 T_CLASS Hash 466102 T_CLASS Array 270880 T_CLASS String 168829 T_CLASS ActionDispatch::Cookies::AbstractCookieJar 155889 T_CLASS Symbol 124974 T_CLASS Numeric 91594 T_CLASS NilClass 83328 T_CLASS Jbuilder::Blank 76853 T_CLASS TrueClass 76213 T_CLASS FalseClass 69976 T_CLASS URI::Generic 62189 T_CLASS ActionController::Parameters 60719 T_CLASS (annon) 57980 T_CLASS (annon) 50100 T_CLASS Concurrent::Collection::MriMapBackend 49742 T_CLASS ActiveSupport::HashWithIndifferentAccess 45199 T_ICLASS src:ActionDispatch::Routing::UrlFor 39851 T_CLASS ActiveRecord::Relation 39836 T_CLASS Proc 39320 T_CLASS BigDecimal 31648 T_CLASS Range 29861 T_CLASS Pathname 29848 T_CLASS ActiveSupport::OrderedOptions
47. Class only linked list Attempt #2
48. Butter fl y Object PP::ObjectMixin Kernel BasicObject ICLASS ICLASS
49. 🫤 Still loops 🫤 Still O(N) 🫤 Still linked list ✅ Simple ✅ No cache invalidation
50. Array Attempt #3
51. Butter fl y Object PP::ObjectMixin Kernel BasicObject ICLASS ICLASS
52. Butter fl y Object PP::ObjectMixin Kernel BasicObject
53. Butter fl y PP::ObjectMixin Kernel BasicObject Object
57. Butter fl y PP::ObjectMixin Kernel BasicObject Object
58. Butter fl y BasicObject Object
59. TypeError Exception Object BasicObject StandardError TypeError is_a? Exception Exception
60. TypeError Exception Object BasicObject StandardError TypeError is_a? Exception Exception
61. TypeError Exception Object BasicObject StandardError TypeError is_a? Exception Exception
62. TypeError Exception Object BasicObject StandardError TypeError is_a? Exception Exception
63. TypeError Exception Object BasicObject StandardError TypeError is_a? Exception Exception
64. TypeError Exception Object BasicObject StandardError TypeError is_a? Exception Exception
65. TypeError Exception Object BasicObject StandardError TypeError is_a? Exception Exception Object BasicObject
66. TypeError Exception Object BasicObject StandardError TypeError is_a? Exception Exception Object BasicObject
67. TypeError Exception Object BasicObject StandardError TypeError is_a? Exception Exception Object BasicObject
68. TypeError Exception Object BasicObject StandardError TypeError is_a? Exception Exception Object BasicObject ✅
69. TypeError Exception Object BasicObject StandardError TypeError is_a? Hash Hash Object BasicObject 🚫
70. TypeError Exception Object BasicObject StandardError TypeError is_a? Integer Numeric Object BasicObject Integer 🚫
71. TypeError Exception Object BasicObject StandardError TypeError is_a? StandardErro Exception Object BasicObject StandardError ✅
72. TypeError Exception Object BasicObject StandardError TypeError is_a? Object Object BasicObject ✅
73. def class_search_superclass(klass, search) depth = search.superclasses.size - 1 klass.superclasses[depth] == search end
74. def class_search_superclass(klass, search) depth = search.superclasses.size - 1 klass.superclasses[depth] == search end ✅ O(1) "constant time" ✅ No loops ✅ No cache invalidation
75. Time-memory trade-off GitHub's largest application: 92k Classes 😳 Memory increase: +6.6 MB Before: ~88MB used by classes
76. Exception Object BasicObject StandardError TypeError Exception Object BasicObject StandardError NameError Exception Object BasicObject StandardError RuntimeError TypeError NameError RuntimeError
77. Exception Object BasicObject StandardError Exception Object BasicObject StandardError Exception Object BasicObject StandardError TypeError NameError RuntimeError
78. Exception Object BasicObject StandardError TypeError NameError RuntimeError
79. Time-memory trade-off GitHub's largest application: 92k Classes 😳 Memory increase: +6.6 MB Memory increase: +1.1 MB Before: ~88MB used by classes
80. def class_search_superclass(klass, search) depth = search.superclasses.size klass.superclasses[depth] == search end
81. def class_search_superclass(klass, search) return true if klass == search depth = search.superclasses.size klass.superclasses[depth] == search end
82. def class_search_superclass(klass, search) return true if klass == search depth = search.superclasses_size return false if klass.superclass_size <= depth klass.superclasses[depth] == search end
83. bool class_search_superclass(VALUE klass, VALUE search) if (klass == search) return true; int depth = search.superclasses_size; if (klass.superclass_size <= depth) return false; return klass.superclasses[depth] == search; end
86. Always faster!
87. thanks ❤
89. Related PRs • https://github.com/ruby/ruby/pull/5568 (fast class checks) • https://github.com/ruby/ruby/pull/5604 (memory reduction)