Hi Ivan I have a simple benchmark that shows that speed improvements start around 5 cases in the switch, and grows about as expected - slow-case is linear in the number of cases, fast-case is approx. constant. There is an approx 50% drop in speed for the fast case somewhere around 80 cases. It's probably a cache-size issue. At that point, we are still 4 times faster than the linear case on average.
The real question is how often the fast-case will happen in real code. Increasing the switch-count also discovered a bug that only triggered if the code buffer grows while the switch is being generated. As for ARM ... it should be appropriate. The generic parts of the code- generations can be shared, so only the assembler parts are different between the two architectures. I am not familiar with ARM assembler, so I can't say how easy it'll be. On Sep 16, 2:17 pm, "Ivan Posva" <[EMAIL PROTECTED]> wrote: > Lasse, > > Do you have synthetic benchmark numbers for these? > > Also please implement the ARM version of this optimization unless you > really feel it is not appropriate on a limited device. I can't think > of a reason not to implement it at the moment. > > Thanks, > -Ivan > > > > On Tue, Sep 16, 2008 at 14:01, <[EMAIL PROTECTED]> wrote: > > > I'd like you to do a code review. To review this change, run > > > gvn review > > --projecthttps://v8.googlecode.com/svn/branches/bleeding_edgelrn/[EMAIL > > PROTECTED] > > > Alternatively, to review the latest snapshot of this change > > branch, run > > > gvn --projecthttps://v8.googlecode.com/svn/branches/bleeding_edgereview > > lrn/jumptable > > > to review the following change: > > > *lrn/[EMAIL PROTECTED] | lrn | 2008-09-16 12:56:29 +-100 (Tue, 16 Sep 2008) > > > Description: > > > Added jump-table operation to assembler. Allows jumping to one of an array > > of labels based on > > a numeric index. > > Used to implement fast-case for switch statement where all lables are > > constant Smi's in a limited > > range. > > > Affected Paths: > > M //branches/bleeding_edge/src/assembler-arm-inl.h > > M //branches/bleeding_edge/src/assembler-ia32-inl.h > > M //branches/bleeding_edge/src/assembler-ia32.cc > > M //branches/bleeding_edge/src/assembler-ia32.h > > M //branches/bleeding_edge/src/assembler.cc > > M //branches/bleeding_edge/src/assembler.h > > M //branches/bleeding_edge/src/codegen-ia32.cc > > M //branches/bleeding_edge/src/disassembler.cc > > A //branches/bleeding_edge/test/mjsunit/switch.js > > > This is a semiautomated message from "gvn mail". See > > <http://code.google.com/p/gvn/> to learn more. > > > Index: src/assembler-arm-inl.h > > =================================================================== > > --- src/assembler-arm-inl.h (^/branches/bleeding_edge/src/[EMAIL > > PROTECTED]) > > > +++ src/assembler-arm-inl.h > > (^/changes/lrn/jumptable/bleeding_edge/src/[EMAIL PROTECTED]) > > > @@ -50,7 +50,13 @@ Condition NegateCondition(Condition cc) { > > > void RelocInfo::apply(int delta) { > > - // We do not use pc relative addressing on ARM, so there is nothing to > > do. > > + if (rmode_ == internal_reference) { > > + // absolute code pointer inside code object moves with the code object. > > + int32_t* p = reinterpret_cast<int32_t*>(pc_); > > + *p += delta; // relocate entry > > + } > > + // We do not use pc relative addressing on ARM, so there is > > + // nothing else to do. > > } > > > Index: src/assembler-ia32-inl.h > > =================================================================== > > --- src/assembler-ia32-inl.h (^/branches/bleeding_edge/src/[EMAIL > > PROTECTED]) > > > +++ src/assembler-ia32-inl.h > > (^/changes/lrn/jumptable/bleeding_edge/src/[EMAIL PROTECTED]) > > > @@ -56,6 +56,10 @@ void RelocInfo::apply(int delta) { > > > // instruction has been inserted). > > int32_t* p = reinterpret_cast<int32_t*>(pc_ + 1); > > *p -= delta; // relocate entry > > + } else if (rmode_ == internal_reference) { > > + // absolute code pointer inside code object moves with the code object. > > + int32_t* p = reinterpret_cast<int32_t*>(pc_); > > + *p += delta; // relocate entry > > } > > } > > > Index: src/assembler-ia32.cc > > =================================================================== > > --- src/assembler-ia32.cc (^/branches/bleeding_edge/src/[EMAIL > > PROTECTED]) > > > +++ src/assembler-ia32.cc > > (^/changes/lrn/jumptable/bleeding_edge/src/[EMAIL PROTECTED]) > > > @@ -151,7 +151,8 @@ void Displacement::init(Label* L, Type type) { > > > const int RelocInfo::kApplyMask = > > - RelocInfo::kCodeTargetMask | 1 << runtime_entry | 1 << js_return; > > + RelocInfo::kCodeTargetMask | 1 << runtime_entry | > > + 1 << js_return | 1 << internal_reference; > > > void RelocInfo::patch_code(byte* instructions, int instruction_count) { > > @@ -1181,7 +1182,13 @@ void Assembler::bind_to(Label* L, int pos) { > > > if (disp.type() == Displacement::UNCONDITIONAL_JUMP) { > > ASSERT(byte_at(fixup_pos - 1) == 0xE9); // jmp expected > > } > > - int imm32 = pos - (fixup_pos + sizeof(int32_t)); > > + int imm32; > > + if (disp.type() == Displacement::ABSOLUTE_ADDRESS) { > > + imm32 = reinterpret_cast<int>(addr_at(pos)); > > + } else { > > + // relative address, relative to point after address > > + imm32 = pos - (fixup_pos + sizeof(int32_t)); > > + } > > long_at_put(fixup_pos, imm32); > > disp.next(L); > > } > > @@ -2016,4 +2023,31 @@ void Assembler::RecordRelocInfo(RelocMode rmode, i > > > } > > > +void Assembler::JumpTable(Label** label_table, int length, Register value) > > { > > + // jump indirect using table > > + Label table_start; > > + // create label linked to absolute address displacement at > > + // disp-part of jump operand > > + Displacement tableDisplacement(&table_start, > > + Displacement::ABSOLUTE_ADDRESS); > > + jmp(Operand(value, times_4, tableDisplacement.data(), > > internal_reference)); > > + table_start.link_to(pc_offset() - sizeof(int32_t)); > > + > > + Align(4); > > + // create the table > > + bind(&table_start); > > + for (int i = 0; i < length; i++) { > > + EnsureSpace ensure_space(this); // can grow arbitrarily much. > > + Label* target = label_table[i]; > > + if (target->is_bound()) { > > + // pointer to position, cast to int > > + uint32_t addr = reinterpret_cast<uint32_t>(addr_at(target->pos())); > > + emit(addr, internal_reference); > > + } else { > > + RecordRelocInfo(internal_reference); > > + emit_disp(target, Displacement::ABSOLUTE_ADDRESS); > > + } > > + } > > +} > > + > > } } // namespace v8::internal > > Index: src/assembler-ia32.h > > =================================================================== > > --- src/assembler-ia32.h (^/branches/bleeding_edge/src/[EMAIL > > PROTECTED]) > > > +++ src/assembler-ia32.h > > (^/changes/lrn/jumptable/bleeding_edge/src/[EMAIL PROTECTED]) > > > @@ -280,13 +280,14 @@ class Operand BASE_EMBEDDED { > > > // > > // Displacement _data field layout > > // > > -// |31.....1|.......0| > > +// |31.....2|1......0| > > // [ next | type | > > > class Displacement BASE_EMBEDDED { > > public: > > enum Type { > > UNCONDITIONAL_JUMP, > > + ABSOLUTE_ADDRESS, > > OTHER > > }; > > > @@ -303,20 +304,22 @@ class Displacement BASE_EMBEDDED { > > > Displacement(Label* L, Type type) { init(L, type); } > > > void print() { > > - PrintF("%s (%x) ", (type() == UNCONDITIONAL_JUMP ? "jmp" : "[other]"), > > + PrintF("%s (%x) ", (type() == UNCONDITIONAL_JUMP ? "jmp" : > > + (type() == ABSOLUTE_ADDRESS ? "ptr" : "[other]")), > > NextField::decode(data_)); > > } > > > private: > > int data_; > > > - class TypeField: public BitField<Type, 0, 1> {}; > > - class NextField: public BitField<int, 1, 32-1> {}; > > + class TypeField: public BitField<Type, 0, 2> {}; > > + class NextField: public BitField<int, 2, 32-2> {}; > > > void init(Label* L, Type type); > > }; > > > + > > // CpuFeatures keeps track of which features are supported by the target > > CPU. > > // Supported features must be enabled by a Scope before use. > > // Example: > > @@ -674,6 +677,12 @@ class Assembler : public Malloced { > > > void RecordPosition(int pos); > > void RecordStatementPosition(int pos); > > > + // Unconditional indirect jump to one of labels in array, based on > > + // value of "index". Index must be in range [0..length-1]. This is > > + // not checked, but should be ensured by the calling code! > > + // Label array must have the required length (at least). > > + void JumpTable(Label** label_table, int length, Register index); > > + > > int pc_offset() const { return pc_ - buffer_; } > > int last_position() const { return last_position_; } > > bool last_position_is_statement() const { > > Index: src/assembler.cc > > =================================================================== > > --- src/assembler.cc (^/branches/bleeding_edge/src/[EMAIL PROTECTED]) > > > +++ src/assembler.cc (^/changes/lrn/jumptable/bleeding_edge/src/[EMAIL > > PROTECTED]) > > > @@ -489,6 +489,7 @@ void RelocInfo::Verify() { > > > case position: > > case statement_position: > > case external_reference: > > + case internal_reference: > > case no_reloc: > > break; > > case reloc_mode_count: > > Index: src/assembler.h > > =================================================================== > > --- src/assembler.h (^/branches/bleeding_edge/src/[EMAIL PROTECTED]) > > > +++ src/assembler.h (^/changes/lrn/jumptable/bleeding_edge/src/[EMAIL > > PROTECTED]) > > > @@ -158,6 +158,8 @@ enum RelocMode { > > > position, // See comment for kNoPosition above. > > statement_position, // See comment for kNoPosition above. > > external_reference, // The address of an external C++ function. > > + internal_reference, // address inside same region (e.g. jump table > > entry) > > + > > // add more as needed > > no_reloc, // never recorded > > > Index: src/codegen-ia32.cc > > =================================================================== > > --- src/codegen-ia32.cc (^/branches/bleeding_edge/src/[EMAIL PROTECTED]) > > > +++ src/codegen-ia32.cc (^/changes/lrn/jumptable/bleeding_edge/src/[EMAIL > > PROTECTED]) > > > @@ -314,6 +314,15 @@ class Ia32CodeGenerator: public CodeGenerator { > > > NODE_LIST(DEF_VISIT) > > #undef DEF_VISIT > > > + // Max ratio of labels-count/label-range for fast table-based Smi switch, > > + // i.e., the sparseness of the jump table. > > + static const int kFastSwitchMaxOverheadPercent = 150; > > + > > + // Create fast switch implementation if all labels are small integers > > + // in a limited range. Returns false if this is not the case, and no > > + // code has been generated (i.e., the default implementation should be > > used). > > + bool FastCaseSwitchStatement(SwitchStatement *switchStmt); > > + > > void RecordStatementPosition(Node* node); > > > // Activation frames. > > @@ -2900,6 +2909,101 @@ void Ia32CodeGenerator::VisitWithExitStatement(Wit > > > } > > > +bool Ia32CodeGenerator::FastCaseSwitchStatement(SwitchStatement *node) { > > + ZoneList<CaseClause*>* cases = > > ... > > read more » --~--~---------~--~----~------------~-------~--~----~ v8-dev mailing list [email protected] http://groups.google.com/group/v8-dev -~----------~----~----~----~------~----~------~--~---
