cpp/openttd-patchpack/source Changeset - r21120:bf4cad9f8d6f

Changeset - r21120:bf4cad9f8d6f

Parent rev.

Child rev.

[Not reviewed]

master

0 7 2

rubidium - 11 years ago 2014-01-02 16:48:16
rubidium@openttd.org

(svn r26205) -Feature: SSE 4.1 sprite sorter, improving the sorting performance significantly (MJP)
For example with GCC 4.8, x86_64 Linux, Intel i5-3337U this patch improves the performance of Pile, Treham and Hamac test save games by about 10% in over-all run time at fast forward at 1920x1080 when zoomed out and when trees are not disabled.

9 files changed with 233 insertions and 27 deletions:

projects/openttd_vs100.vcxproj

projects/openttd_vs100.vcxproj.filters

projects/openttd_vs80.vcproj

projects/openttd_vs90.vcproj

source.list

src/openttd.cpp

src/viewport.cpp

src/viewport_sprite_sorter.h

src/viewport_sprite_sorter_sse4.cpp

109

0 comments (0 inline, 0 general)

projects/openttd_vs100.vcxproj

➞

Show inline comments

@@ @@ -382,12 +382,13 @@ @@
     <ClCompile Include="..\src\tile_map.cpp" />
     <ClCompile Include="..\src\tilearea.cpp" />
     <ClCompile Include="..\src\townname.cpp" />
     <ClCompile Include="..\src\vehicle.cpp" />
     <ClCompile Include="..\src\vehiclelist.cpp" />
     <ClCompile Include="..\src\viewport.cpp" />
     <ClCompile Include="..\src\viewport_sprite_sorter_sse4.cpp" />
     <ClCompile Include="..\src\waypoint.cpp" />
     <ClCompile Include="..\src\widget.cpp" />
     <ClCompile Include="..\src\window.cpp" />
     <ClInclude Include="..\src\aircraft.h" />
     <ClInclude Include="..\src\airport.h" />
     <ClInclude Include="..\src\animated_tile_func.h" />
@@ @@ -638,12 +639,13 @@ @@
     <ClInclude Include="..\src\vehicle_func.h" />
     <ClInclude Include="..\src\vehicle_gui.h" />
     <ClInclude Include="..\src\vehicle_gui_base.h" />
     <ClInclude Include="..\src\vehicle_type.h" />
     <ClInclude Include="..\src\vehiclelist.h" />
     <ClInclude Include="..\src\viewport_func.h" />
     <ClInclude Include="..\src\viewport_sprite_sorter.h" />
     <ClInclude Include="..\src\viewport_type.h" />
     <ClInclude Include="..\src\water.h" />
     <ClInclude Include="..\src\waypoint_base.h" />
     <ClInclude Include="..\src\waypoint_func.h" />
     <ClInclude Include="..\src\widget_type.h" />
     <ClInclude Include="..\src\os\windows\win32.h" />

projects/openttd_vs100.vcxproj.filters

➞

Show inline comments

@@ @@ -381,12 +381,15 @@ @@
     <ClCompile Include="..\src\vehiclelist.cpp">
       <Filter>Source Files</Filter>
     </ClCompile>
     <ClCompile Include="..\src\viewport.cpp">
       <Filter>Source Files</Filter>
     </ClCompile>
     <ClCompile Include="..\src\viewport_sprite_sorter_sse4.cpp">
       <Filter>Source Files</Filter>
     </ClCompile>
     <ClCompile Include="..\src\waypoint.cpp">
       <Filter>Source Files</Filter>
     </ClCompile>
     <ClCompile Include="..\src\widget.cpp">
       <Filter>Source Files</Filter>
     </ClCompile>
@@ @@ -1149,12 +1152,15 @@ @@
     <ClInclude Include="..\src\vehiclelist.h">
       <Filter>Header Files</Filter>
     </ClInclude>
     <ClInclude Include="..\src\viewport_func.h">
       <Filter>Header Files</Filter>
     </ClInclude>
     <ClInclude Include="..\src\viewport_sprite_sorter.h">
       <Filter>Header Files</Filter>
     </ClInclude>
     <ClInclude Include="..\src\viewport_type.h">
       <Filter>Header Files</Filter>
     </ClInclude>
     <ClInclude Include="..\src\water.h">
       <Filter>Header Files</Filter>
     </ClInclude>

projects/openttd_vs80.vcproj

➞

Show inline comments

@@ @@ -808,12 +808,16 @@ @@
 			</File>
 			<File
 				RelativePath=".\..\src\viewport.cpp"
+				>
 			</File>
 			<File
 				RelativePath=".\..\src\viewport_sprite_sorter_sse4.cpp"
+				>
 			</File>
 			<File
 				RelativePath=".\..\src\waypoint.cpp"
+				>
 			</File>
 			<File
 				RelativePath=".\..\src\widget.cpp"
+				>
@@ @@ -1836,12 +1840,16 @@ @@
 			</File>
 			<File
 				RelativePath=".\..\src\viewport_func.h"
+				>
 			</File>
 			<File
 				RelativePath=".\..\src\viewport_sprite_sorter.h"
+				>
 			</File>
 			<File
 				RelativePath=".\..\src\viewport_type.h"
+				>
 			</File>
 			<File
 				RelativePath=".\..\src\water.h"
+				>

projects/openttd_vs90.vcproj

➞

Show inline comments

@@ @@ -805,12 +805,16 @@ @@
 			</File>
 			<File
 				RelativePath=".\..\src\viewport.cpp"
+				>
 			</File>
 			<File
 				RelativePath=".\..\src\viewport_sprite_sorter_sse4.cpp"
+				>
 			</File>
 			<File
 				RelativePath=".\..\src\waypoint.cpp"
+				>
 			</File>
 			<File
 				RelativePath=".\..\src\widget.cpp"
+				>
@@ @@ -1833,12 +1837,16 @@ @@
 			</File>
 			<File
 				RelativePath=".\..\src\viewport_func.h"
+				>
 			</File>
 			<File
 				RelativePath=".\..\src\viewport_sprite_sorter.h"
+				>
 			</File>
 			<File
 				RelativePath=".\..\src\viewport_type.h"
+				>
 			</File>
 			<File
 				RelativePath=".\..\src\water.h"
+				>

source.list

➞

Show inline comments

@@ @@ -108,12 +108,15 @@ townname.cpp @@
 		#end
 	#end
 #end
 vehicle.cpp
 vehiclelist.cpp
 viewport.cpp
 #if SSE
 viewport_sprite_sorter_sse4.cpp
 #end
 waypoint.cpp
 widget.cpp
 window.cpp
 # Header Files
 #if ALLEGRO
@@ @@ -371,12 +374,13 @@ vehicle_base.h @@
 vehicle_func.h
 vehicle_gui.h
 vehicle_gui_base.h
 vehicle_type.h
 vehiclelist.h
 viewport_func.h
 viewport_sprite_sorter.h
 viewport_type.h
 water.h
 waypoint_base.h
 waypoint_func.h
 widget_type.h
 os/windows/win32.h

src/openttd.cpp

➞

Show inline comments

@@ @@ -59,19 +59,18 @@ @@
 #include "misc/getoptdata.h"
 #include "game/game.hpp"
 #include "game/game_config.hpp"
 #include "town.h"
 #include "subsidy_func.h"
 #include "gfx_layout.h"
+#include "viewport_sprite_sorter.h"
 #include "linkgraph/linkgraphschedule.h"
 #include <stdarg.h>
 void CallLandscapeTick();
 void IncreaseDate();
 void DoPaletteAnimations();
 void MusicLoop();
 void ResetMusic();
 void CallWindowTickEvent();
@@ @@ -772,12 +771,14 @@ int openttd_main(int argc, char *argv[]) @@
 		StrEmpty(videodriver) ?
 			usererror("Failed to autoprobe video driver") :
 			usererror("Failed to select requested video driver '%s'", videodriver);
+	}
 	free(videodriver);
 	InitializeSpriteSorter();
 	/* Initialize the zoom level of the screen to normal */
 	_screen.zoom = ZOOM_LVL_NORMAL;
 	NetworkStartUp(); // initialize network-core
 #if defined(ENABLE_NETWORK)

src/viewport.cpp

➞

Show inline comments

@@ @@ -43,12 +43,13 @@ @@
 #include "company_func.h"
 #include "waypoint_func.h"
 #include "window_func.h"
 #include "tilehighlight_func.h"
 #include "window_gui.h"
 #include "linkgraph/linkgraph_gui.h"
 #include "viewport_sprite_sorter.h"
 #include "table/strings.h"
 #include "table/palettes.h"
 Point _tile_fract_coords;
@@ @@ -75,35 +76,12 @@ struct ChildScreenSpriteToDraw { @@
 	const SubSprite *sub;           ///< only draw a rectangular part of the sprite
 	int32 x;
 	int32 y;
 	int next;                       ///< next child to draw (-1 at the end)
 };
 /** Parent sprite that should be drawn */
 struct ParentSpriteToDraw {
 	SpriteID image;                 ///< sprite to draw
 	PaletteID pal;                  ///< palette to use
 	const SubSprite *sub;           ///< only draw a rectangular part of the sprite
 	int32 x;                        ///< screen X coordinate of sprite
 	int32 y;                        ///< screen Y coordinate of sprite
 	int32 left;                     ///< minimal screen X coordinate of sprite (= x + sprite->x_offs), reference point for child sprites
 	int32 top;                      ///< minimal screen Y coordinate of sprite (= y + sprite->y_offs), reference point for child sprites
 	int32 xmin;                     ///< minimal world X coordinate of bounding box
 	int32 xmax;                     ///< maximal world X coordinate of bounding box
 	int32 ymin;                     ///< minimal world Y coordinate of bounding box
 	int32 ymax;                     ///< maximal world Y coordinate of bounding box
 	int zmin;                       ///< minimal world Z coordinate of bounding box
 	int zmax;                       ///< maximal world Z coordinate of bounding box
 	int first_child;                ///< the first child to draw.
 	bool comparison_done;           ///< Used during sprite sorting: true if sprite has been compared with all other sprites
 };
 /** Enumeration of multi-part foundations */
 enum FoundationPart {
 	FOUNDATION_PART_NONE     = 0xFF,  ///< Neither foundation nor groundsprite drawn yet.
 	FOUNDATION_PART_NORMAL   = 0,     ///< First part (normal foundation or no foundation)
 	FOUNDATION_PART_HALFTILE = 1,     ///< Second part (halftile foundation)
 	FOUNDATION_PART_END
@@ @@ -119,13 +97,12 @@ enum SpriteCombineMode { @@
 	SPRITE_COMBINE_ACTIVE,   ///< %Sprite combining is active. #AddSortableSpriteToDraw outputs child sprites.
 };
 typedef SmallVector<TileSpriteToDraw, 64> TileSpriteToDrawVector;
 typedef SmallVector<StringSpriteToDraw, 4> StringSpriteToDrawVector;
 typedef SmallVector<ParentSpriteToDraw, 64> ParentSpriteToDrawVector;
 typedef SmallVector<ParentSpriteToDraw*, 64> ParentSpriteToSortVector;
 typedef SmallVector<ChildScreenSpriteToDraw, 16> ChildScreenSpriteToDrawVector;
 /** Data structure storing rendering information */
 struct ViewportDrawer {
 	DrawPixelInfo dpi;
@@ @@ -151,12 +128,13 @@ static ViewportDrawer _vd; @@
 TileHighlightData _thd;
 static TileInfo *_cur_ti;
 bool _draw_bounding_boxes = false;
 bool _draw_dirty_blocks = false;
 uint _dirty_block_colour = 0;
 static VpSpriteSorter _vp_sprite_sorter = NULL;
 static Point MapXYZToViewport(const ViewPort *vp, int x, int y, int z)
+{
 	Point p = RemapCoords(x, y, z);
 	p.x -= vp->virtual_width / 2;
 	p.y -= vp->virtual_height / 2;
@@ @@ -1285,12 +1263,18 @@ static void ViewportDrawTileSprites(cons @@
 	const TileSpriteToDraw *tsend = tstdv->End();
 	for (const TileSpriteToDraw *ts = tstdv->Begin(); ts != tsend; ++ts) {
 		DrawSpriteViewport(ts->image, ts->pal, ts->x, ts->y, ts->sub);
+	}
+}
 /** This fallback sprite checker always exists. */
 static bool ViewportSortParentSpritesChecker()
+{
 	return true;
+}
 /** Sort parent sprites pointer array */
 static void ViewportSortParentSprites(ParentSpriteToSortVector *psdv)
+{
 	ParentSpriteToDraw **psdvend = psdv->End();
 	ParentSpriteToDraw **psd = psdv->Begin();
 	while (psd != psdvend) {
@@ @@ -1477,13 +1461,13 @@ void ViewportDoDraw(const ViewPort *vp, @@
 	ParentSpriteToDraw *psd_end = _vd.parent_sprites_to_draw.End();
 	for (ParentSpriteToDraw *it = _vd.parent_sprites_to_draw.Begin(); it != psd_end; it++) {
 		*_vd.parent_sprites_to_sort.Append() = it;
+	}
-	ViewportSortParentSprites(&_vd.parent_sprites_to_sort);
+	_vp_sprite_sorter(&_vd.parent_sprites_to_sort);
 	ViewportDrawParentSprites(&_vd.parent_sprites_to_sort, &_vd.child_screen_sprites_to_draw);
 	if (_draw_bounding_boxes) ViewportDrawBoundingBoxes(&_vd.parent_sprites_to_sort);
 	if (_draw_dirty_blocks) ViewportDrawDirtyBlocks();
 	DrawPixelInfo dp = _vd.dpi;
@@ @@ -2995,6 +2979,32 @@ Point GetViewportStationMiddle(const Vie @@
 	Point p = RemapCoords(x, y, z);
 	p.x = UnScaleByZoom(p.x - vp->virtual_left, vp->zoom) + vp->left;
 	p.y = UnScaleByZoom(p.y - vp->virtual_top, vp->zoom) + vp->top;
 	return p;
+}
 /** Helper class for getting the best sprite sorter. */
 struct ViewportSSCSS {
 	VpSorterChecker fct_checker; ///< The check function.
 	VpSpriteSorter fct_sorter;   ///< The sorting function.
 };
 /** List of sorters ordered from best to worst. */
 static ViewportSSCSS _vp_sprite_sorters[] = {
 #ifdef WITH_SSE
 	{ &ViewportSortParentSpritesSSE41Checker, &ViewportSortParentSpritesSSE41 },
 #endif
 	{ &ViewportSortParentSpritesChecker, &ViewportSortParentSprites }
 };
 /** Choose the "best" sprite sorter and set _vp_sprite_sorter. */
 void InitializeSpriteSorter()
+{
 	for (uint i = 0; i < lengthof(_vp_sprite_sorters); i++) {
 		if (_vp_sprite_sorters[i].fct_checker()) {
 			_vp_sprite_sorter = _vp_sprite_sorters[i].fct_sorter;
 			break;
+		}
+	}
 	assert(_vp_sprite_sorter != NULL);
+}

src/viewport_sprite_sorter.h

➞

Show inline comments

@@ new file 100644 @@
 /* $Id$ */
 /*
  * This file is part of OpenTTD.
  * OpenTTD is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, version 2.
  * OpenTTD is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
  * See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with OpenTTD. If not, see <http://www.gnu.org/licenses/>.
  */
 /** @file viewport_sprite_sorter.h Types related to sprite sorting. */
 #include "stdafx.h"
 #include "core/smallvec_type.hpp"
 #include "gfx_type.h"
 #ifndef VIEWPORT_SPRITE_SORTER_H
 #define VIEWPORT_SPRITE_SORTER_H
 /** Parent sprite that should be drawn */
 struct ParentSpriteToDraw {
 	/* Block of 16B loadable in xmm register */
 	int32 xmin;                     ///< minimal world X coordinate of bounding box
 	int32 ymin;                     ///< minimal world Y coordinate of bounding box
 	int32 zmin;                     ///< minimal world Z coordinate of bounding box
 	int32 x;                        ///< screen X coordinate of sprite
 	/* Second block of 16B loadable in xmm register */
 	int32 xmax;                     ///< maximal world X coordinate of bounding box
 	int32 ymax;                     ///< maximal world Y coordinate of bounding box
 	int32 zmax;                     ///< maximal world Z coordinate of bounding box
 	int32 y;                        ///< screen Y coordinate of sprite
 	SpriteID image;                 ///< sprite to draw
 	PaletteID pal;                  ///< palette to use
 	const SubSprite *sub;           ///< only draw a rectangular part of the sprite
 	int32 left;                     ///< minimal screen X coordinate of sprite (= x + sprite->x_offs), reference point for child sprites
 	int32 top;                      ///< minimal screen Y coordinate of sprite (= y + sprite->y_offs), reference point for child sprites
 	int first_child;                ///< the first child to draw.
 	bool comparison_done;           ///< Used during sprite sorting: true if sprite has been compared with all other sprites
 };
 typedef SmallVector<ParentSpriteToDraw*, 64> ParentSpriteToSortVector;
 /** Type for method for checking whether a viewport sprite sorter exists. */
 typedef bool (*VpSorterChecker)();
 /** Type for the actual viewport sprite sorter. */
 typedef void (*VpSpriteSorter)(ParentSpriteToSortVector *psd);
 #ifdef WITH_SSE
 bool ViewportSortParentSpritesSSE41Checker();
 void ViewportSortParentSpritesSSE41(ParentSpriteToSortVector *psdv);
 #endif
 void InitializeSpriteSorter();
 #endif /* VIEWPORT_SPRITE_SORTER_H */

src/viewport_sprite_sorter_sse4.cpp

➞

Show inline comments

@@ new file 100644 @@
 /* $Id$ */
 /*
  * This file is part of OpenTTD.
  * OpenTTD is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, version 2.
  * OpenTTD is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
  * See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with OpenTTD. If not, see <http://www.gnu.org/licenses/>.
  */
 /** @file viewport_sprite_sorter_sse.cpp Sprite sorter that uses SSE4.1. */
 #ifdef WITH_SSE
 #include "stdafx.h"
 #include "cpu.h"
 #include "smmintrin.h"
 #include "viewport_sprite_sorter.h"
 #ifdef _SQ64
 	assert_compile((sizeof(ParentSpriteToDraw) % 16) == 0);
 	#define LOAD_128 _mm_load_si128
 #else
 	#define LOAD_128 _mm_loadu_si128
 #endif
 /** Sort parent sprites pointer array using SSE4.1 optimizations. */
 void ViewportSortParentSpritesSSE41(ParentSpriteToSortVector *psdv)
+{
 	const __m128i mask_ptest = _mm_setr_epi8(-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,  0,  0,  0,  0);
 	ParentSpriteToDraw ** const psdvend = psdv->End();
 	ParentSpriteToDraw **psd = psdv->Begin();
 	while (psd != psdvend) {
 		ParentSpriteToDraw * const ps = *psd;
 		if (ps->comparison_done) {
 			psd++;
 			continue;
+		}
 		ps->comparison_done = true;
 		for (ParentSpriteToDraw **psd2 = psd + 1; psd2 != psdvend; psd2++) {
 			ParentSpriteToDraw * const ps2 = *psd2;
 			if (ps2->comparison_done) continue;
 			/*
 			 * Decide which comparator to use, based on whether the bounding boxes overlap
+			 *
 			 * Original code:
 			 * if (ps->xmax >= ps2->xmin && ps->xmin <= ps2->xmax && // overlap in X?
 			 *     ps->ymax >= ps2->ymin && ps->ymin <= ps2->ymax && // overlap in Y?
 			 *     ps->zmax >= ps2->zmin && ps->zmin <= ps2->zmax) { // overlap in Z?
+			 *
 			 * Above conditions are equivalent to:
 			 * 1/    !( (ps->xmax >= ps2->xmin) && (ps->ymax >= ps2->ymin) && (ps->zmax >= ps2->zmin)   &&    (ps->xmin <= ps2->xmax) && (ps->ymin <= ps2->ymax) && (ps->zmin <= ps2->zmax) )
 			 * 2/    !( (ps->xmax >= ps2->xmin) && (ps->ymax >= ps2->ymin) && (ps->zmax >= ps2->zmin)   &&    (ps2->xmax >= ps->xmin) && (ps2->ymax >= ps->ymin) && (ps2->zmax >= ps->zmin) )
 			 * 3/  !( ( (ps->xmax >= ps2->xmin) && (ps->ymax >= ps2->ymin) && (ps->zmax >= ps2->zmin) ) &&  ( (ps2->xmax >= ps->xmin) && (ps2->ymax >= ps->ymin) && (ps2->zmax >= ps->zmin) ) )
 			 * 4/ !( !( (ps->xmax <  ps2->xmin) || (ps->ymax <  ps2->ymin) || (ps->zmax <  ps2->zmin) ) && !( (ps2->xmax <  ps->xmin) || (ps2->ymax <  ps->ymin) || (ps2->zmax <  ps->zmin) ) )
 			 * 5/ PTEST <---------------------------------- rslt1 ---------------------------------->         <------------------------------ rslt2 -------------------------------------->
 			 */
 			__m128i ps1_max = LOAD_128((__m128i*) &ps->xmax);
 			__m128i ps2_min = LOAD_128((__m128i*) &ps2->xmin);
 			__m128i rslt1 = _mm_cmplt_epi32(ps1_max, ps2_min);
 			if (!_mm_testz_si128(mask_ptest, rslt1))
 				continue;
 			__m128i ps1_min = LOAD_128((__m128i*) &ps->xmin);
 			__m128i ps2_max = LOAD_128((__m128i*) &ps2->xmax);
 			__m128i rslt2 = _mm_cmplt_epi32(ps2_max, ps1_min);
 			if (_mm_testz_si128(mask_ptest, rslt2)) {
 				/* Use X+Y+Z as the sorting order, so sprites closer to the bottom of
 				 * the screen and with higher Z elevation, are drawn in front.
 				 * Here X,Y,Z are the coordinates of the "center of mass" of the sprite,
 				 * i.e. X=(left+right)/2, etc.
 				 * However, since we only care about order, don't actually divide / 2
 				 */
 				if (ps->xmin + ps->xmax + ps->ymin + ps->ymax + ps->zmin + ps->zmax <=
 						ps2->xmin + ps2->xmax + ps2->ymin + ps2->ymax + ps2->zmin + ps2->zmax) {
 					continue;
+				}
+			}
 			/* Move ps2 in front of ps */
 			ParentSpriteToDraw * const temp = ps2;
 			for (ParentSpriteToDraw **psd3 = psd2; psd3 > psd; psd3--) {
 				*psd3 = *(psd3 - 1);
+			}
 			*psd = temp;
+		}
+	}
+}
 /**
  * Check whether the current CPU supports SSE 4.1.
  * @return True iff the CPU supports SSE 4.1.
  */
 bool ViewportSortParentSpritesSSE41Checker()
+{
 	int cpu_info[4] = {-1};
 	ottd_cpuid(cpu_info, 0);
 	unsigned int max_info_type = cpu_info[0];
 	if (max_info_type < 1) return false;
 	ottd_cpuid(cpu_info, 1);
 	return (cpu_info[2] & (1 << 19)) != 0;
+}
 #endif /* WITH_SSE */

0 comments (0 inline, 0 general)