Performance thresholds are defined for operators in a flow graph for a streaming application. A streams manager deploys the flow graph to one or more virtual machines (VMs). The performance of each portion of the flow graph on each VM is monitored. A VM is selected. When the performance of the portion of the flow graph in the selected VM does not satisfy the defined performance threshold(s), a determination is made regarding whether the portion of the flow graph is underperforming or overperforming. When the portion of the flow graph is underperforming, the portion of the flow graph is split into multiple portions that are implemented on multiple VMs. When the portion of the flow graph is overperforming, a determination is made of whether a neighbor VM is also overperforming. When a neighbor VM is also overperforming, the two VMs may be coalesced into a single VM.