• Binbin's avatar
    Optimize PSUBSCRIBE and PUNSUBSCRIBE from O(N*M) to O(N) (#12298) · b5106249
    Binbin authored
    In the original implementation, the time complexity of the commands
    is actually O(N*M), where N is the number of patterns the client is
    already subscribed and M is the number of patterns to subscribe to.
    The docs are all wrong about this.
    
    Specifically, because the original client->pubsub_patterns is a list,
    so we need to do listSearchKey which is O(N). In this PR, we change it
    to a dict, so the search becomes O(1).
    
    At the same time, both pubsub_channels and pubsubshard_channels are dicts.
    Changing pubsub_patterns to a dictionary improves the readability and
    maintainability of the code.
    b5106249
networking.c 175 KB