Mercurial > hg > truffle
comparison src/share/vm/memory/binaryTreeDictionary.cpp @ 8003:3c9bc17b9403
Merge
author | bpittore |
---|---|
date | Thu, 07 Feb 2013 16:05:48 -0500 |
parents | 3c327c2b6782 db9981fd3124 |
children | de88570fabfc |
comparison
equal
deleted
inserted
replaced
7989:454d7cc622ab | 8003:3c9bc17b9403 |
---|---|
21 * questions. | 21 * questions. |
22 * | 22 * |
23 */ | 23 */ |
24 | 24 |
25 #include "precompiled.hpp" | 25 #include "precompiled.hpp" |
26 #include "utilities/macros.hpp" | |
26 #include "gc_implementation/shared/allocationStats.hpp" | 27 #include "gc_implementation/shared/allocationStats.hpp" |
27 #include "memory/binaryTreeDictionary.hpp" | 28 #include "memory/binaryTreeDictionary.hpp" |
28 #include "memory/freeList.hpp" | 29 #include "memory/freeList.hpp" |
29 #include "memory/freeBlockDictionary.hpp" | 30 #include "memory/freeBlockDictionary.hpp" |
30 #include "memory/metablock.hpp" | 31 #include "memory/metablock.hpp" |
31 #include "memory/metachunk.hpp" | 32 #include "memory/metachunk.hpp" |
32 #include "runtime/globals.hpp" | 33 #include "runtime/globals.hpp" |
33 #include "utilities/ostream.hpp" | 34 #include "utilities/ostream.hpp" |
34 #ifndef SERIALGC | 35 #include "utilities/macros.hpp" |
36 #if INCLUDE_ALL_GCS | |
35 #include "gc_implementation/concurrentMarkSweep/adaptiveFreeList.hpp" | 37 #include "gc_implementation/concurrentMarkSweep/adaptiveFreeList.hpp" |
36 #include "gc_implementation/concurrentMarkSweep/freeChunk.hpp" | 38 #include "gc_implementation/concurrentMarkSweep/freeChunk.hpp" |
37 #include "gc_implementation/shared/spaceDecorator.hpp" | 39 #include "gc_implementation/shared/spaceDecorator.hpp" |
38 #include "gc_implementation/concurrentMarkSweep/freeChunk.hpp" | 40 #include "gc_implementation/concurrentMarkSweep/freeChunk.hpp" |
39 #endif // SERIALGC | 41 #endif // INCLUDE_ALL_GCS |
40 | 42 |
41 //////////////////////////////////////////////////////////////////////////////// | 43 //////////////////////////////////////////////////////////////////////////////// |
42 // A binary tree based search structure for free blocks. | 44 // A binary tree based search structure for free blocks. |
43 // This is currently used in the Concurrent Mark&Sweep implementation. | 45 // This is currently used in the Concurrent Mark&Sweep implementation. |
44 //////////////////////////////////////////////////////////////////////////////// | 46 //////////////////////////////////////////////////////////////////////////////// |
116 TreeList<Chunk_t, FreeList_t>* tl = TreeList<Chunk_t, FreeList_t>::as_TreeList(tc); | 118 TreeList<Chunk_t, FreeList_t>* tl = TreeList<Chunk_t, FreeList_t>::as_TreeList(tc); |
117 return tl; | 119 return tl; |
118 } | 120 } |
119 | 121 |
120 | 122 |
121 #ifndef SERIALGC | 123 #if INCLUDE_ALL_GCS |
122 // Specialize for AdaptiveFreeList which tries to avoid | 124 // Specialize for AdaptiveFreeList which tries to avoid |
123 // splitting a chunk of a size that is under populated in favor of | 125 // splitting a chunk of a size that is under populated in favor of |
124 // an over populated size. The general get_better_list() just returns | 126 // an over populated size. The general get_better_list() just returns |
125 // the current list. | 127 // the current list. |
126 template <> | 128 template <> |
158 } | 160 } |
159 } | 161 } |
160 } | 162 } |
161 return curTL; | 163 return curTL; |
162 } | 164 } |
163 #endif // SERIALGC | 165 #endif // INCLUDE_ALL_GCS |
164 | 166 |
165 template <class Chunk_t, template <class> class FreeList_t> | 167 template <class Chunk_t, template <class> class FreeList_t> |
166 TreeList<Chunk_t, FreeList_t>* | 168 TreeList<Chunk_t, FreeList_t>* |
167 TreeList<Chunk_t, FreeList_t>::get_better_list( | 169 TreeList<Chunk_t, FreeList_t>::get_better_list( |
168 BinaryTreeDictionary<Chunk_t, FreeList_t>* dictionary) { | 170 BinaryTreeDictionary<Chunk_t, FreeList_t>* dictionary) { |
869 } | 871 } |
870 | 872 |
871 template <class Chunk_t, template <class> class FreeList_t> | 873 template <class Chunk_t, template <class> class FreeList_t> |
872 void BinaryTreeDictionary<Chunk_t, FreeList_t>::dict_census_update(size_t size, bool split, bool birth){} | 874 void BinaryTreeDictionary<Chunk_t, FreeList_t>::dict_census_update(size_t size, bool split, bool birth){} |
873 | 875 |
874 #ifndef SERIALGC | 876 #if INCLUDE_ALL_GCS |
875 template <> | 877 template <> |
876 void AFLBinaryTreeDictionary::dict_census_update(size_t size, bool split, bool birth){ | 878 void AFLBinaryTreeDictionary::dict_census_update(size_t size, bool split, bool birth){ |
877 TreeList<FreeChunk, AdaptiveFreeList>* nd = find_list(size); | 879 TreeList<FreeChunk, AdaptiveFreeList>* nd = find_list(size); |
878 if (nd) { | 880 if (nd) { |
879 if (split) { | 881 if (split) { |
898 // This is a death where the appropriate list is now | 900 // This is a death where the appropriate list is now |
899 // empty and has been removed from the list. | 901 // empty and has been removed from the list. |
900 // This is a birth associated with a LinAB. The chunk | 902 // This is a birth associated with a LinAB. The chunk |
901 // for the LinAB is not in the dictionary. | 903 // for the LinAB is not in the dictionary. |
902 } | 904 } |
903 #endif // SERIALGC | 905 #endif // INCLUDE_ALL_GCS |
904 | 906 |
905 template <class Chunk_t, template <class> class FreeList_t> | 907 template <class Chunk_t, template <class> class FreeList_t> |
906 bool BinaryTreeDictionary<Chunk_t, FreeList_t>::coal_dict_over_populated(size_t size) { | 908 bool BinaryTreeDictionary<Chunk_t, FreeList_t>::coal_dict_over_populated(size_t size) { |
907 // For the general type of freelists, encourage coalescing by | 909 // For the general type of freelists, encourage coalescing by |
908 // returning true. | 910 // returning true. |
909 return true; | 911 return true; |
910 } | 912 } |
911 | 913 |
912 #ifndef SERIALGC | 914 #if INCLUDE_ALL_GCS |
913 template <> | 915 template <> |
914 bool AFLBinaryTreeDictionary::coal_dict_over_populated(size_t size) { | 916 bool AFLBinaryTreeDictionary::coal_dict_over_populated(size_t size) { |
915 if (FLSAlwaysCoalesceLarge) return true; | 917 if (FLSAlwaysCoalesceLarge) return true; |
916 | 918 |
917 TreeList<FreeChunk, AdaptiveFreeList>* list_of_size = find_list(size); | 919 TreeList<FreeChunk, AdaptiveFreeList>* list_of_size = find_list(size); |
918 // None of requested size implies overpopulated. | 920 // None of requested size implies overpopulated. |
919 return list_of_size == NULL || list_of_size->coal_desired() <= 0 || | 921 return list_of_size == NULL || list_of_size->coal_desired() <= 0 || |
920 list_of_size->count() > list_of_size->coal_desired(); | 922 list_of_size->count() > list_of_size->coal_desired(); |
921 } | 923 } |
922 #endif // SERIALGC | 924 #endif // INCLUDE_ALL_GCS |
923 | 925 |
924 // Closures for walking the binary tree. | 926 // Closures for walking the binary tree. |
925 // do_list() walks the free list in a node applying the closure | 927 // do_list() walks the free list in a node applying the closure |
926 // to each free chunk in the list | 928 // to each free chunk in the list |
927 // do_tree() walks the nodes in the binary tree applying do_list() | 929 // do_tree() walks the nodes in the binary tree applying do_list() |
977 _inter_sweep_estimate(inter_sweep_estimate), | 979 _inter_sweep_estimate(inter_sweep_estimate), |
978 _intra_sweep_estimate(intra_sweep_estimate) { } | 980 _intra_sweep_estimate(intra_sweep_estimate) { } |
979 | 981 |
980 void do_list(FreeList<Chunk_t>* fl) {} | 982 void do_list(FreeList<Chunk_t>* fl) {} |
981 | 983 |
982 #ifndef SERIALGC | 984 #if INCLUDE_ALL_GCS |
983 void do_list(AdaptiveFreeList<Chunk_t>* fl) { | 985 void do_list(AdaptiveFreeList<Chunk_t>* fl) { |
984 double coalSurplusPercent = _percentage; | 986 double coalSurplusPercent = _percentage; |
985 fl->compute_desired(_inter_sweep_current, _inter_sweep_estimate, _intra_sweep_estimate); | 987 fl->compute_desired(_inter_sweep_current, _inter_sweep_estimate, _intra_sweep_estimate); |
986 fl->set_coal_desired((ssize_t)((double)fl->desired() * coalSurplusPercent)); | 988 fl->set_coal_desired((ssize_t)((double)fl->desired() * coalSurplusPercent)); |
987 fl->set_before_sweep(fl->count()); | 989 fl->set_before_sweep(fl->count()); |
988 fl->set_bfr_surp(fl->surplus()); | 990 fl->set_bfr_surp(fl->surplus()); |
989 } | 991 } |
990 #endif // SERIALGC | 992 #endif // INCLUDE_ALL_GCS |
991 }; | 993 }; |
992 | 994 |
993 // Used to search the tree until a condition is met. | 995 // Used to search the tree until a condition is met. |
994 // Similar to TreeCensusClosure but searches the | 996 // Similar to TreeCensusClosure but searches the |
995 // tree and returns promptly when found. | 997 // tree and returns promptly when found. |
1132 double percentage; | 1134 double percentage; |
1133 public: | 1135 public: |
1134 setTreeSurplusClosure(double v) { percentage = v; } | 1136 setTreeSurplusClosure(double v) { percentage = v; } |
1135 void do_list(FreeList<Chunk_t>* fl) {} | 1137 void do_list(FreeList<Chunk_t>* fl) {} |
1136 | 1138 |
1137 #ifndef SERIALGC | 1139 #if INCLUDE_ALL_GCS |
1138 void do_list(AdaptiveFreeList<Chunk_t>* fl) { | 1140 void do_list(AdaptiveFreeList<Chunk_t>* fl) { |
1139 double splitSurplusPercent = percentage; | 1141 double splitSurplusPercent = percentage; |
1140 fl->set_surplus(fl->count() - | 1142 fl->set_surplus(fl->count() - |
1141 (ssize_t)((double)fl->desired() * splitSurplusPercent)); | 1143 (ssize_t)((double)fl->desired() * splitSurplusPercent)); |
1142 } | 1144 } |
1143 #endif // SERIALGC | 1145 #endif // INCLUDE_ALL_GCS |
1144 }; | 1146 }; |
1145 | 1147 |
1146 template <class Chunk_t, template <class> class FreeList_t> | 1148 template <class Chunk_t, template <class> class FreeList_t> |
1147 void BinaryTreeDictionary<Chunk_t, FreeList_t>::set_tree_surplus(double splitSurplusPercent) { | 1149 void BinaryTreeDictionary<Chunk_t, FreeList_t>::set_tree_surplus(double splitSurplusPercent) { |
1148 setTreeSurplusClosure<Chunk_t, FreeList_t> sts(splitSurplusPercent); | 1150 setTreeSurplusClosure<Chunk_t, FreeList_t> sts(splitSurplusPercent); |
1155 size_t hint; | 1157 size_t hint; |
1156 public: | 1158 public: |
1157 setTreeHintsClosure(size_t v) { hint = v; } | 1159 setTreeHintsClosure(size_t v) { hint = v; } |
1158 void do_list(FreeList<Chunk_t>* fl) {} | 1160 void do_list(FreeList<Chunk_t>* fl) {} |
1159 | 1161 |
1160 #ifndef SERIALGC | 1162 #if INCLUDE_ALL_GCS |
1161 void do_list(AdaptiveFreeList<Chunk_t>* fl) { | 1163 void do_list(AdaptiveFreeList<Chunk_t>* fl) { |
1162 fl->set_hint(hint); | 1164 fl->set_hint(hint); |
1163 assert(fl->hint() == 0 || fl->hint() > fl->size(), | 1165 assert(fl->hint() == 0 || fl->hint() > fl->size(), |
1164 "Current hint is inconsistent"); | 1166 "Current hint is inconsistent"); |
1165 if (fl->surplus() > 0) { | 1167 if (fl->surplus() > 0) { |
1166 hint = fl->size(); | 1168 hint = fl->size(); |
1167 } | 1169 } |
1168 } | 1170 } |
1169 #endif // SERIALGC | 1171 #endif // INCLUDE_ALL_GCS |
1170 }; | 1172 }; |
1171 | 1173 |
1172 template <class Chunk_t, template <class> class FreeList_t> | 1174 template <class Chunk_t, template <class> class FreeList_t> |
1173 void BinaryTreeDictionary<Chunk_t, FreeList_t>::set_tree_hints(void) { | 1175 void BinaryTreeDictionary<Chunk_t, FreeList_t>::set_tree_hints(void) { |
1174 setTreeHintsClosure<Chunk_t, FreeList_t> sth(0); | 1176 setTreeHintsClosure<Chunk_t, FreeList_t> sth(0); |
1178 // Save count before previous sweep and splits and coalesces. | 1180 // Save count before previous sweep and splits and coalesces. |
1179 template <class Chunk_t, template <class> class FreeList_t> | 1181 template <class Chunk_t, template <class> class FreeList_t> |
1180 class clearTreeCensusClosure : public AscendTreeCensusClosure<Chunk_t, FreeList_t> { | 1182 class clearTreeCensusClosure : public AscendTreeCensusClosure<Chunk_t, FreeList_t> { |
1181 void do_list(FreeList<Chunk_t>* fl) {} | 1183 void do_list(FreeList<Chunk_t>* fl) {} |
1182 | 1184 |
1183 #ifndef SERIALGC | 1185 #if INCLUDE_ALL_GCS |
1184 void do_list(AdaptiveFreeList<Chunk_t>* fl) { | 1186 void do_list(AdaptiveFreeList<Chunk_t>* fl) { |
1185 fl->set_prev_sweep(fl->count()); | 1187 fl->set_prev_sweep(fl->count()); |
1186 fl->set_coal_births(0); | 1188 fl->set_coal_births(0); |
1187 fl->set_coal_deaths(0); | 1189 fl->set_coal_deaths(0); |
1188 fl->set_split_births(0); | 1190 fl->set_split_births(0); |
1189 fl->set_split_deaths(0); | 1191 fl->set_split_deaths(0); |
1190 } | 1192 } |
1191 #endif // SERIALGC | 1193 #endif // INCLUDE_ALL_GCS |
1192 }; | 1194 }; |
1193 | 1195 |
1194 template <class Chunk_t, template <class> class FreeList_t> | 1196 template <class Chunk_t, template <class> class FreeList_t> |
1195 void BinaryTreeDictionary<Chunk_t, FreeList_t>::clear_tree_census(void) { | 1197 void BinaryTreeDictionary<Chunk_t, FreeList_t>::clear_tree_census(void) { |
1196 clearTreeCensusClosure<Chunk_t, FreeList_t> ctc; | 1198 clearTreeCensusClosure<Chunk_t, FreeList_t> ctc; |
1250 fl->print_on(gclog_or_tty); | 1252 fl->print_on(gclog_or_tty); |
1251 _total_free += fl->count() * fl->size() ; | 1253 _total_free += fl->count() * fl->size() ; |
1252 total()->set_count( total()->count() + fl->count() ); | 1254 total()->set_count( total()->count() + fl->count() ); |
1253 } | 1255 } |
1254 | 1256 |
1255 #ifndef SERIALGC | 1257 #if INCLUDE_ALL_GCS |
1256 void do_list(AdaptiveFreeList<Chunk_t>* fl) { | 1258 void do_list(AdaptiveFreeList<Chunk_t>* fl) { |
1257 if (++_print_line >= 40) { | 1259 if (++_print_line >= 40) { |
1258 FreeList_t<Chunk_t>::print_labels_on(gclog_or_tty, "size"); | 1260 FreeList_t<Chunk_t>::print_labels_on(gclog_or_tty, "size"); |
1259 _print_line = 0; | 1261 _print_line = 0; |
1260 } | 1262 } |
1269 total()->set_coal_births( total()->coal_births() + fl->coal_births() ); | 1271 total()->set_coal_births( total()->coal_births() + fl->coal_births() ); |
1270 total()->set_coal_deaths( total()->coal_deaths() + fl->coal_deaths() ); | 1272 total()->set_coal_deaths( total()->coal_deaths() + fl->coal_deaths() ); |
1271 total()->set_split_births(total()->split_births() + fl->split_births()); | 1273 total()->set_split_births(total()->split_births() + fl->split_births()); |
1272 total()->set_split_deaths(total()->split_deaths() + fl->split_deaths()); | 1274 total()->set_split_deaths(total()->split_deaths() + fl->split_deaths()); |
1273 } | 1275 } |
1274 #endif // SERIALGC | 1276 #endif // INCLUDE_ALL_GCS |
1275 }; | 1277 }; |
1276 | 1278 |
1277 template <class Chunk_t, template <class> class FreeList_t> | 1279 template <class Chunk_t, template <class> class FreeList_t> |
1278 void BinaryTreeDictionary<Chunk_t, FreeList_t>::print_dict_census(void) const { | 1280 void BinaryTreeDictionary<Chunk_t, FreeList_t>::print_dict_census(void) const { |
1279 | 1281 |
1284 | 1286 |
1285 FreeList_t<Chunk_t>* total = ptc.total(); | 1287 FreeList_t<Chunk_t>* total = ptc.total(); |
1286 FreeList_t<Chunk_t>::print_labels_on(gclog_or_tty, " "); | 1288 FreeList_t<Chunk_t>::print_labels_on(gclog_or_tty, " "); |
1287 } | 1289 } |
1288 | 1290 |
1289 #ifndef SERIALGC | 1291 #if INCLUDE_ALL_GCS |
1290 template <> | 1292 template <> |
1291 void AFLBinaryTreeDictionary::print_dict_census(void) const { | 1293 void AFLBinaryTreeDictionary::print_dict_census(void) const { |
1292 | 1294 |
1293 gclog_or_tty->print("\nBinaryTree\n"); | 1295 gclog_or_tty->print("\nBinaryTree\n"); |
1294 AdaptiveFreeList<FreeChunk>::print_labels_on(gclog_or_tty, "size"); | 1296 AdaptiveFreeList<FreeChunk>::print_labels_on(gclog_or_tty, "size"); |
1306 - total->split_deaths() - total->coal_deaths()) | 1308 - total->split_deaths() - total->coal_deaths()) |
1307 /(total->prev_sweep() != 0 ? (double)total->prev_sweep() : 1.0), | 1309 /(total->prev_sweep() != 0 ? (double)total->prev_sweep() : 1.0), |
1308 (double)(total->desired() - total->count()) | 1310 (double)(total->desired() - total->count()) |
1309 /(total->desired() != 0 ? (double)total->desired() : 1.0)); | 1311 /(total->desired() != 0 ? (double)total->desired() : 1.0)); |
1310 } | 1312 } |
1311 #endif // SERIALGC | 1313 #endif // INCLUDE_ALL_GCS |
1312 | 1314 |
1313 template <class Chunk_t, template <class> class FreeList_t> | 1315 template <class Chunk_t, template <class> class FreeList_t> |
1314 class PrintFreeListsClosure : public AscendTreeCensusClosure<Chunk_t, FreeList_t> { | 1316 class PrintFreeListsClosure : public AscendTreeCensusClosure<Chunk_t, FreeList_t> { |
1315 outputStream* _st; | 1317 outputStream* _st; |
1316 int _print_line; | 1318 int _print_line; |
1412 template class TreeList<Metachunk, FreeList>; | 1414 template class TreeList<Metachunk, FreeList>; |
1413 template class BinaryTreeDictionary<Metachunk, FreeList>; | 1415 template class BinaryTreeDictionary<Metachunk, FreeList>; |
1414 template class TreeChunk<Metachunk, FreeList>; | 1416 template class TreeChunk<Metachunk, FreeList>; |
1415 | 1417 |
1416 | 1418 |
1417 #ifndef SERIALGC | 1419 #if INCLUDE_ALL_GCS |
1418 // Explicitly instantiate these types for FreeChunk. | 1420 // Explicitly instantiate these types for FreeChunk. |
1419 template class TreeList<FreeChunk, AdaptiveFreeList>; | 1421 template class TreeList<FreeChunk, AdaptiveFreeList>; |
1420 template class BinaryTreeDictionary<FreeChunk, AdaptiveFreeList>; | 1422 template class BinaryTreeDictionary<FreeChunk, AdaptiveFreeList>; |
1421 template class TreeChunk<FreeChunk, AdaptiveFreeList>; | 1423 template class TreeChunk<FreeChunk, AdaptiveFreeList>; |
1422 | 1424 |
1423 #endif // SERIALGC | 1425 #endif // INCLUDE_ALL_GCS |