Thanks for the answers. I expected that the way I was creating/deleting buffers was not optimal, but didn't expected such huge gap in timing. More than 500 times slower seems like a lot. I will try to be smarter with how I use buffers.
I did a "not real test that doesn't mean anything": I created lots of buffers, bound them and uploaded data to them (never delete) and measure the time spent for the uploads. I did it with 1000 uploads of 256Ko and 1000 uploads of 1024Ko.
This test is not accurate or anything but there seems that there is a pattern of spikes every 16 Mo.
I then added a second loop that would write to the same buffers, but with glBufferSubData instead of glBufferData (writing the same amount of byte in the buffers). Most write were faster (like 10 times faster) but every 16 Mo the timing was not improved (and since other were faster, it a huge gap). But it is faster because it's the second time I'm writing in it. If I write a second time with glBufferData, the time is the same as with glBufferSubData. So next I let every test run several times.
And then I did 1000 glBufferSubData in 1 buffer (initialized with a glBufferData passing the total size and 0 as the data pointer): the same result as the test above, with huge spike every 16 Mo.
glBufferData_256k.txt The 3 tests are one after the other.
If I didn't do something stupid in those tests, it seems that even if I handle buffer differently, at some point I would get one long frame. I guess I have to try and see.
PS: I didn't read the pdf Jesse posted yet.