Sequencer custom task scheduler hangs when a task graph exceeds 512 tasks with Clang (TDynamicSparseBitSet::IsBitSet uses the wrong bit index)

Summary

With Sequencer.CustomTaskScheduling enabled, a large sequence can hang the game thread in FEntitySystemScheduler::ExecuteTasks. We hit it in a cutscene whose scheduler graph had 528 tasks, mostly children of UMovieSceneSkeletalAnimationSystem’s forked task. Setting Sequencer.CustomTaskScheduling 0 avoids it.

Root cause

FTaskBitSet is TDynamicSparseBitSet<uint32, TDynamicSparseBitSetBucketStorage<uint16, 0>>, which stores 512 bits per bucket. TDynamicSparseBitSet::SetBit converts the bit index to an offset within its bucket before calling into the bucket. TDynamicSparseBitSet::IsBitSet does not convert; it passes the absolute index:

if (EntrPtr[EntryIndex].Offset == Bucket)
{
    return EntrPtr[EntryIndex].Bits.IsBitSet(Bit); // Bit is absolute, should be bucket-relative
}

For bit 512 and up, TFixedSparseBitSet::IsBitSet then computes HashType(1) << (BitIndex / BucketSize) with a shift of 32 or more on a uint32. That’s undefined behavior, so the result depends on the compiler, Clang return the wrong answers.

FEntitySystemScheduler::AddPrerequisite relies on ComputedSubsequents.IsBitSet to avoid counting the same dependency twice. With wrong results, a task’s NumPrerequisites no longer matches the number of tasks that will actually signal it. Its WaitCount never reaches zero and ExecuteTasks never returns. Every task we saw stuck had an index of 512 or higher.

Second bug in the same class

TDynamicSparseBitSet::operator|= silently drops any of Other’s entries whose bucket offset is beyond this set’s last entry. Once the merge loop reaches the end of this, the remaining Other entries are never appended. For example, {bucket 0} |= {bucket 0, bucket 1} loses bucket 1. FEntitySystemScheduler::PropagatePrerequisite uses this operator, so system-to-system dependencies on tasks with index 512 and up can be lost.

Suggested fixes (Engine/Source/Runtime/MovieScene/Public/Containers/SparseBitSet.h)

// TDynamicSparseBitSet::IsBitSet
if (EntrPtr[EntryIndex].Offset == Bucket)
{
    return EntrPtr[EntryIndex].Bits.IsBitSet(Bit - Bucket*NumBitsInBucket);
}

// TDynamicSparseBitSet::operator|=, after the merge loop, before 'return *this;'
if (OtherIndex < Other.Entries.Num())
{
    Entries.Append(Other.Entries.GetData() + OtherIndex, Other.Entries.Num() - OtherIndex);
}

This issue didn’t occur 100% of the time, but it was frequent enough. After these changes I could no longer repro.

This post [Content removed] sounds related. I confirmed we had those fixes.

Is this a reasonable fix?

[Attachment Removed]

After looking at this again, a more obvious fix would be to mimic SetBit in IsBitSet and use `Bit -= Bucket*NumBitsInBucket;` just after calculating the Bucket and leave `return EntrPtr[EntryIndex].Bits.IsBitSet(Bit);` alone.

[Attachment Removed]

Hi,

Thanks, this was a great find, and your analysis is spot on. I’ve applied both fixes exactly as you suggested, using the Bit -= Bucket*NumBitsInBucket version for IsBitSet.

I’ve opened an internal Jira with Propose Public checked so you can track it: UE-402072. I’ll follow up once the fix is submitted.

Thanks again.

[Attachment Removed]