core: tune performance total ordering (#66)

- the checking of `internal stability` is more expensive than checking `len(ANS) == validatorCount`. So only check it when `len(ANS) != validatorCount`.
- cache the result of `grade` between candidates.
- cache the `acking height vector` of each candidate.
- add test on total ordering with different acking frequency between blocks.

2 files changed, 61 insertions, 0 deletions

diff --git a/core/test/blocks-generator.go b/core/test/blocks-generator.go
index a26a901..3cd97ee 100644
--- a/core/test/blocks-generator.go
+++ b/core/test/blocks-generator.go
@@ -189,6 +189,12 @@ func normalAckingCountGenerator(
 	}
 }
 
+// MaxAckingCountGenerator return generator which returns
+// fixed maximum acking count.
+func MaxAckingCountGenerator(count int) func() int {
+	return func() int { return count }
+}
+
 // generateValidatorPicker is a function generator, which would generate
 // a function to randomly pick one validator ID from a slice of validator ID.
 func generateValidatorPicker() func([]types.ValidatorID) types.ValidatorID {
diff --git a/core/test/blocks-generator_test.go b/core/test/blocks-generator_test.go
index 0624da2..43e994f 100644
--- a/core/test/blocks-generator_test.go
+++ b/core/test/blocks-generator_test.go
@@ -103,6 +103,61 @@ func (s *BlocksGeneratorTestCase) TestGenerate() {
 	}
 }
 
+func (s *BlocksGeneratorTestCase) TestGenerateWithMaxAckCount() {
+	var (
+		validatorCount = 13
+		blockCount     = 50
+		gen            = NewBlocksGenerator(nil, stableRandomHash)
+		req            = s.Require()
+	)
+
+	// Generate with 0 acks.
+	db, err := blockdb.NewMemBackedBlockDB()
+	req.Nil(err)
+	req.Nil(gen.Generate(
+		validatorCount, blockCount, MaxAckingCountGenerator(0), db))
+	// Load blocks to check their acking count.
+	iter, err := db.GetAll()
+	req.Nil(err)
+	for {
+		block, err := iter.Next()
+		if err == blockdb.ErrIterationFinished {
+			break
+		}
+		req.Nil(err)
+		if block.IsGenesis() {
+			continue
+		}
+		req.Len(block.Acks, 1)
+	}
+
+	// Generate with acks as many as possible.
+	db, err = blockdb.NewMemBackedBlockDB()
+	req.Nil(err)
+	req.Nil(gen.Generate(
+		validatorCount, blockCount, MaxAckingCountGenerator(
+			validatorCount), db))
+	// Load blocks to verify the average acking count.
+	totalAckingCount := 0
+	totalBlockCount := 0
+	iter, err = db.GetAll()
+	req.Nil(err)
+	for {
+		block, err := iter.Next()
+		if err == blockdb.ErrIterationFinished {
+			break
+		}
+		req.Nil(err)
+		if block.IsGenesis() {
+			continue
+		}
+		totalAckingCount += len(block.Acks)
+		totalBlockCount++
+	}
+	req.NotZero(totalBlockCount)
+	req.True((totalAckingCount / totalBlockCount) >= (validatorCount / 2))
+}
+
 func TestBlocksGenerator(t *testing.T) {
 	suite.Run(t, new(BlocksGeneratorTestCase))
 }