Matplotlib animation : adding / removing legend item slows down animations

Question

The code below dynamically add some lines and their legend in a matlplot lib animated plot. I have an issue with the legend adding : it significantly reduces the frame rate.

Let's describe the issue. The root question was how to update legend in order to see the newly added plot legend? I've tried several options :

1- Add line, try to add legend calling ax.legend()

lines.append(ax.plot(x, np.sin(x), label='line {}'.format(len(lines)))[0]) 
legend = ax.legend(loc='upper left')

Result : legend not updated. Frame rate does not change significantly when the lines are added. It's not what I want, I cannot see the legends of added lines

2- Add line and return legend in animation update function

lines.append(ax.plot(x, np.sin(x), label='line {}'.format(len(lines)))[0]) 
legend = ax.legend(loc='upper left')

# Forcing legend redraw by returning it in update function updates it    
ret = *lines, legend,

Result : legend updated. Frame rate significantly drops when the lines are added. If I try to only update legend once (by returning *lines, legend, once after new plot added), I can see 1 frame with the updated legend, then we cannot see anymore the legend in the next frames.

The code :

import numpy as np
import time
import matplotlib.pyplot as plt
import matplotlib.animation as animation
import time
from threading import Thread, Lock

VIZ_UPDATE_FS = 50
ADD_LEGEND_IN_BLIT = True

fig, ax = plt.subplots()

f = 10
x = np.arange(0, 2*np.pi, 0.01)
lines = []
lines.append(ax.plot(x, np.sin(x), label='line {}'.format(len(lines)))[0])
legend = ax.legend(loc='upper left')
t_fps_start = time.time()
fps_nb_frames = 0

def animate(i):
    global fps_nb_frames, t_fps_start
    fps_nb_frames += 1
    with add_line_mutex:
        for j, line in enumerate(lines):
            line.set_ydata(np.sin(x + i/((j + 1)*10.0)))  # update the data
        # reset FPS counter to get precise fps measurements
        if not t_fps_start or (time.time() - t_fps_start) > 10:
            t_fps_start = time.time()
            fps_nb_frames = 0
            print('reset FPS counter')
        # Measure FPS after 5s an until 1 min
        if time.time() - t_fps_start > 3:
            print('VIZ fps = {:.1f}'.format(fps_nb_frames/(time.time() - t_fps_start)))
        if ADD_LEGEND_IN_BLIT or i%100 == 0:
            ret = *lines, legend,
        else:
            ret = *lines,
        return ret

def add_line():
    global legend
    t_0 = time.time()
    while not stop_th_run and len(lines) < 15:
        if int(time.time() - t_0) > 0.2:
            t_0 = time.time()
            with add_line_mutex:
                lines.append(ax.plot(x, np.sin(x), label='line {}'.format(len(lines)))[0])
                legend = ax.legend(loc='upper left')
        time.sleep(0.1)

ani = animation.FuncAnimation(fig, animate, np.arange(1, 200), 
                              interval=1/VIZ_UPDATE_FS*1000, blit=True)
add_line_th = Thread(target=add_line)
add_line_mutex = Lock()
stop_th_run = False
add_line_th.start()
plt.show()
stop_th_run = True
while add_line_th.is_alive():
    time.sleep(0.1)

How can we add dynamically a line and its corresponding legend keeping a decent framerate?