Re: [4/5] d3dx9: Implement D3DXMESHOPT_ATTRSORT vertex reordering.

[Matteo Bruni]

2011/5/6 Dylan Smith <dylan.ah.smith(a)gmail.com>:
> +struct vertex_attrib_duplication {
> +    DWORD attrib;
> +    DWORD vertex_index;
> +    struct vertex_attrib_duplication *ptr;
> +};
> ...
> +            struct vertex_attrib_duplication **heads = NULL; /* head of list for each vertex */

You probably want to use Wine lists (from include/wine/list.h) instead
of your own implementation.
> +            heads = HeapAlloc(GetProcessHeap(), 0, This->numvertices * sizeof(*heads) + max_entries * sizeof(*duplications));
> +            duplications = (struct vertex_attrib_duplication *)(heads + This->numvertices);

I'm not sure why you are usually sticking together many arrays in a
single allocation. Economizing on the number of HeapAllocs is not a
great reason IMHO.

[4/5] d3dx9: Implement D3DXMESHOPT_ATTRSORT vertex reordering.

[Dylan Smith]

On Sun, May 8, 2011 at 3:18 PM, Matteo Bruni <matteo.mystral(a)gmail.com>wrote:
> 2011/5/6 Dylan Smith <dylan.ah.smith(a)gmail.com>:
> > +struct vertex_attrib_duplication {
> > +    DWORD attrib;
> > +    DWORD vertex_index;
> > +    struct vertex_attrib_duplication *ptr;
> > +};
> > ...
> > +            struct vertex_attrib_duplication **heads = NULL; /* head of
> > list for each vertex */
>
> You probably want to use Wine lists (from include/wine/list.h) instead
> of your own implementation.
>
> I only wanted a singly linked list.  The back links would be unused, but
> would waste memory and update operations.  The linked list also gets
> invalidated by sorting, so the ptr field is actually also used to store the
> original position in the array for performing a stable sort. I don't think
> using include/wine/list.h would make the code clearer, since it would be
> like trying to abstract the implementation details, when those details are
> relevant to the implementation (see the answer to the next question for an
> example).
> +            heads = HeapAlloc(GetProcessHeap(), 0, This->numvertices *
> sizeof(*heads) + max_entries * sizeof(*duplications));
> > +            duplications = (struct vertex_attrib_duplication *)(heads +
> > This->numvertices);
>
> I'm not sure why you are usually sticking together many arrays in a
> single allocation. Economizing on the number of HeapAllocs is not a
> great reason IMHO.

Reducing memory allocations and keeping locality of memory references seemed
like a good idea, but in this case it actually affects the behaviour of the
sort. The pointer values are used in vertex_attrib_compare as a secondary
value, which largely affects the result since many vertices share the same
attribute value.  Pointers into the heads array are used to keep the first
use of each vertex in the original order of the vertices, and duplications
of those vertices must be sorted using a stable sort, so their original
position in the array are compared where the attribute value is the same.

[4/5] d3dx9: Implement D3DXMESHOPT_ATTRSORT vertex reordering.

[Matteo Bruni]

2011/5/8 Dylan Smith <dylan.ah.smith(a)gmail.com>:
> On Sun, May 8, 2011 at 3:18 PM, Matteo Bruni <matteo.mystral(a)gmail.com>
> wrote:
> > 2011/5/6 Dylan Smith <dylan.ah.smith(a)gmail.com>:
> > > +struct vertex_attrib_duplication {
> > > +    DWORD attrib;
> > > +    DWORD vertex_index;
> > > +    struct vertex_attrib_duplication *ptr;
> > > +};
> > > ...
> > > +            struct vertex_attrib_duplication **heads = NULL; /* head of
> > > list for each vertex */
> >
> > You probably want to use Wine lists (from include/wine/list.h) instead
> > of your own implementation.
>
> I only wanted a singly linked list.  The back links would be unused, but
> would waste memory and update operations.  The linked list also gets
> invalidated by sorting, so the ptr field is actually also used to store the
> original position in the array for performing a stable sort. I don't think
> using include/wine/list.h would make the code clearer, since it would be
> like trying to abstract the implementation details, when those details are
> relevant to the implementation (see the answer to the next question for an
> example).

It is an ongoing effort (almost complete I think) to replace custom
list implementations with the generic one through the Wine codebase. I
don't think this case is so special to require a custom list. I don't
have a strong opinion here, but, e.g., I don't find adding one or two
fields to the structure a big drawback.
> > > +            heads = HeapAlloc(GetProcessHeap(), 0, This->numvertices *
> > > sizeof(*heads) + max_entries * sizeof(*duplications));
> > > +            duplications = (struct vertex_attrib_duplication *)(heads +
> > > This->numvertices);
> >
> > I'm not sure why you are usually sticking together many arrays in a
> > single allocation. Economizing on the number of HeapAllocs is not a
> > great reason IMHO.
>
> Reducing memory allocations and keeping locality of memory references seemed
> like a good idea, but in this case it actually affects the behaviour of the
> sort. The pointer values are used in vertex_attrib_compare as a secondary
> value, which largely affects the result since many vertices share the same
> attribute value.  Pointers into the heads array are used to keep the first
> use of each vertex in the original order of the vertices, and duplications
> of those vertices must be sorted using a stable sort, so their original
> position in the array are compared where the attribute value is the same.

I was referring to allocating "heads" and "duplications" from the same
call, which, as far as I can see, is not required.
Regarding the sorting requirements, those can also be addressed by
adding another index field to the structure.