The data structure is a (memory) heap... there appears to be one in mesa/main/mm.h. There's also one in nouveau_heap.h which is quite simple and totally unreliant on nouveau, just happens to be there. How hard would it be to integrate something like that?
The trouble with adding slow things is that you forget about them, and they're not _that_ slow, but this stuff adds up. -ilia On Tue, Jan 19, 2016 at 6:05 AM, Lofstedt, Marta <marta.lofst...@intel.com> wrote: > This seem a bit suboptimal, since the same space is potentially searched > multiple times. However, I believe that a better solution would be to use > some other data structure which would probably require quite a big effort, so > for now, this is: > > Reviewed-by: Marta Lofstedt <marta.lofst...@intel.com> > > >> -----Original Message----- >> From: mesa-dev [mailto:mesa-dev-boun...@lists.freedesktop.org] On >> Behalf Of Tapani Pälli >> Sent: Tuesday, January 19, 2016 11:17 AM >> To: mesa-dev@lists.freedesktop.org >> Subject: [Mesa-dev] [PATCH v2] glsl: move uniform calculation to >> link_uniforms >> >> Patch moves uniform calculation to happen during link_uniforms, this is >> possible with help of UniformRemapTable that has all the reserved locations. >> >> Location assignment for implicit locations is changed so that we utilize also >> the 'holes' that explicit uniform location assignment might have left in >> UniformRemapTable, this makes it possible to fit more uniforms as >> previously we were lazy here and wasting space. >> >> Fixes following CTS tests: >> ES31-CTS.explicit_uniform_location.uniform-loc-mix-with-implicit-max >> ES31-CTS.explicit_uniform_location.uniform-loc-mix-with-implicit-max- >> array >> >> v2: code cleanups (Matt), increment NumUniformRemapTable correctly >> (Timothy), fix find_empty_block to work like intended (sigh) and >> add some more comments. >> >> Signed-off-by: Tapani Pälli <tapani.pa...@intel.com> >> --- >> src/glsl/link_uniforms.cpp | 87 >> ++++++++++++++++++++++++++++++++++++++++------ >> src/glsl/linker.cpp | 19 ++++------ >> src/glsl/linker.h | 3 +- >> 3 files changed, 85 insertions(+), 24 deletions(-) >> >> diff --git a/src/glsl/link_uniforms.cpp b/src/glsl/link_uniforms.cpp index >> 33b2d4c..76ee70d 100644 >> --- a/src/glsl/link_uniforms.cpp >> +++ b/src/glsl/link_uniforms.cpp >> @@ -1057,9 +1057,40 @@ assign_hidden_uniform_slot_id(const char >> *name, unsigned hidden_id, >> uniform_size->map->put(hidden_uniform_start + hidden_id, name); } >> >> +/** >> + * Search UniformRemapTable for empty block big enough to hold given >> uniform. >> + * TODO Optimize this algorithm later if it turns out to be a major >> bottleneck. >> + */ >> +static int >> +find_empty_block(struct gl_shader_program *prog, >> + struct gl_uniform_storage *uniform) { >> + const unsigned entries = MAX2(1, uniform->array_elements); >> + for (unsigned i = 0, j; i < prog->NumUniformRemapTable; i++) { >> + /* We found empty space in UniformRemapTable. */ >> + if (prog->UniformRemapTable[i] == NULL) { >> + for (j = i; j < entries && j < prog->NumUniformRemapTable; j++) { >> + if (prog->UniformRemapTable[j] != NULL) { >> + /* Entries do not fit in this space, continue searching >> + * after this location. >> + */ >> + i = j + 1; >> + break; >> + } >> + } >> + /* Entries fit, we can return this location. */ >> + if (i != j + 1) { >> + return i; >> + } >> + } >> + } >> + return -1; >> +} >> + >> void >> link_assign_uniform_locations(struct gl_shader_program *prog, >> - unsigned int boolean_true) >> + unsigned int boolean_true, >> + unsigned int max_locations) >> { >> ralloc_free(prog->UniformStorage); >> prog->UniformStorage = NULL; >> @@ -1150,6 +1181,20 @@ link_assign_uniform_locations(struct >> gl_shader_program *prog, >> >> parcel_out_uniform_storage parcel(prog->UniformHash, uniforms, data); >> >> + unsigned total_entries = 0; >> + >> + /* Calculate amount of 'holes' left after explicit locations were >> + * reserved from UniformRemapTable. >> + */ >> + unsigned empty_locs = 0; >> + for (unsigned i = 0; i < prog->NumUniformRemapTable; i++) >> + if (prog->UniformRemapTable[i] == NULL) >> + empty_locs++; >> + >> + /* Add all the reserved explicit locations - empty locations in remap >> table. >> */ >> + if (prog->NumUniformRemapTable) >> + total_entries = (prog->NumUniformRemapTable - 1) - empty_locs; >> + >> for (unsigned i = 0; i < MESA_SHADER_STAGES; i++) { >> if (prog->_LinkedShaders[i] == NULL) >> continue; >> @@ -1213,21 +1258,43 @@ link_assign_uniform_locations(struct >> gl_shader_program *prog, >> /* how many new entries for this uniform? */ >> const unsigned entries = MAX2(1, uniforms[i].array_elements); >> >> - /* resize remap table to fit new entries */ >> - prog->UniformRemapTable = >> - reralloc(prog, >> - prog->UniformRemapTable, >> - gl_uniform_storage *, >> - prog->NumUniformRemapTable + entries); >> + /* Find UniformRemapTable for empty blocks where we can fit this >> uniform. */ >> + int chosen_location = -1; >> + >> + if (empty_locs) >> + chosen_location = find_empty_block(prog, &uniforms[i]); >> + >> + if (chosen_location != -1) { >> + empty_locs -= entries; >> + } else { >> + chosen_location = prog->NumUniformRemapTable; >> + >> + /* Add new entries to the total amount of entries. */ >> + total_entries += entries; >> + >> + /* resize remap table to fit new entries */ >> + prog->UniformRemapTable = >> + reralloc(prog, >> + prog->UniformRemapTable, >> + gl_uniform_storage *, >> + prog->NumUniformRemapTable + entries); >> + prog->NumUniformRemapTable += entries; >> + } >> >> /* set pointers for this uniform */ >> for (unsigned j = 0; j < entries; j++) >> - prog->UniformRemapTable[prog->NumUniformRemapTable+j] = >> &uniforms[i]; >> + prog->UniformRemapTable[chosen_location + j] = &uniforms[i]; >> >> /* set the base location in remap table for the uniform */ >> - uniforms[i].remap_location = prog->NumUniformRemapTable; >> + uniforms[i].remap_location = chosen_location; >> + } >> >> - prog->NumUniformRemapTable += entries; >> + /* Verify that total amount of entries for explicit and implicit >> locations >> + * is less than MAX_UNIFORM_LOCATIONS. >> + */ >> + if (total_entries >= max_locations) { >> + linker_error(prog, "count of uniform locations >= >> MAX_UNIFORM_LOCATIONS" >> + "(%u >= %u)", total_entries, max_locations); >> } >> >> /* Reserve all the explicit locations of the active subroutine uniforms. >> */ >> diff --git a/src/glsl/linker.cpp b/src/glsl/linker.cpp index 6657777..5be8d9f >> 100644 >> --- a/src/glsl/linker.cpp >> +++ b/src/glsl/linker.cpp >> @@ -3146,7 +3146,6 @@ check_explicit_uniform_locations(struct gl_context >> *ctx, >> return; >> } >> >> - unsigned entries_total = 0; >> for (unsigned i = 0; i < MESA_SHADER_STAGES; i++) { >> struct gl_shader *sh = prog->_LinkedShaders[i]; >> >> @@ -3158,8 +3157,6 @@ check_explicit_uniform_locations(struct gl_context >> *ctx, >> if (!var || var->data.mode != ir_var_uniform) >> continue; >> >> - entries_total += var->type->uniform_locations(); >> - >> if (var->data.explicit_location) { >> bool ret; >> if (var->type->without_array()->is_subroutine()) >> @@ -3173,15 +3170,6 @@ check_explicit_uniform_locations(struct >> gl_context *ctx, >> } >> } >> } >> - >> - /* Verify that total amount of entries for explicit and implicit >> locations >> - * is less than MAX_UNIFORM_LOCATIONS. >> - */ >> - if (entries_total >= ctx->Const.MaxUserAssignableUniformLocations) { >> - linker_error(prog, "count of uniform locations >= >> MAX_UNIFORM_LOCATIONS" >> - "(%u >= %u)", entries_total, >> - ctx->Const.MaxUserAssignableUniformLocations); >> - } >> delete uniform_map; >> } >> >> @@ -4556,7 +4544,12 @@ link_shaders(struct gl_context *ctx, struct >> gl_shader_program *prog) >> goto done; >> >> update_array_sizes(prog); >> - link_assign_uniform_locations(prog, ctx->Const.UniformBooleanTrue); >> + link_assign_uniform_locations(prog, ctx->Const.UniformBooleanTrue, >> + >> + ctx->Const.MaxUserAssignableUniformLocations); >> + >> + if (!prog->LinkStatus) >> + goto done; >> + >> link_assign_atomic_counter_resources(ctx, prog); >> store_fragdepth_layout(prog); >> >> diff --git a/src/glsl/linker.h b/src/glsl/linker.h index c80be1c..76f95c0 >> 100644 >> --- a/src/glsl/linker.h >> +++ b/src/glsl/linker.h >> @@ -35,7 +35,8 @@ link_invalidate_variable_locations(exec_list *ir); >> >> extern void >> link_assign_uniform_locations(struct gl_shader_program *prog, >> - unsigned int boolean_true); >> + unsigned int boolean_true, >> + unsigned int max_locations); >> >> extern void >> link_set_uniform_initializers(struct gl_shader_program *prog, >> -- >> 2.5.0 >> >> _______________________________________________ >> mesa-dev mailing list >> mesa-dev@lists.freedesktop.org >> http://lists.freedesktop.org/mailman/listinfo/mesa-dev > _______________________________________________ > mesa-dev mailing list > mesa-dev@lists.freedesktop.org > http://lists.freedesktop.org/mailman/listinfo/mesa-dev _______________________________________________ mesa-dev mailing list mesa-dev@lists.freedesktop.org http://lists.freedesktop.org/mailman/listinfo/mesa-dev
